#P4971. 再次实现平等Ⅱ
-
ID: 3854
传统题
1000ms
128MiB
尝试: 101
已通过: 29
难度: 6
上传者:
再次实现平等Ⅱ
Description
你有一个由 n 个整数组成的数组 a。你可以进行无数次以下操作：选择三个整数 i , j, x (1<=i<=j<=n )，并将数组中索引为 i 至 j的所有元素赋值为 x 。这个操作的代价取决于所选的索引，等于 (j-i+1)的值。
例如，数组等于 [1, 2, 3, 4, 5, 1] 。如果我们选择i = 2, j = 4, x = 8 ，那么执行此操作后，数组将等于 [1, 8, 8, 8, 5, 1] 。
要使数组中的所有元素相等，最少需要花费多少代价？
Input Format
第一行包含一个整数 n ( 1≤n≤2e5 ) ，表示数组的大小。第二行包含 n 个整数 a1,a2,…,an( 0≤ai≤n ) ，表示数组里每一个元素。
Output Format
输出一个整数 ，表示使数组中所有元素相等所需的最小代价。6
1 2 3 4 5 14