题目描述

你有一个由 n 个整数组成的数组 a。

你可以最多 1 次进行以下操作：选择三个整数 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]。

要使数组中的所有元素相等，最少需要花费多少代价？

输入格式

第一行包含一个整数 n (1≤n≤2e5)，表示数组的大小。

第二行包含 n 个整数 a₁, a₂, …, aₙ (1≤aᵢ≤n)，表示数组里每一个元素。

输出格式

输出一个整数，表示使数组中所有元素相等所需的最小代价。

样例输入

6
1 2 3 4 5 1

样例输出

4

样例解释

数组初始为 [1, 2, 3, 4, 5, 1]。要使所有元素相等，最优方案是选择将索引 2 到 5（对应值 2, 3, 4, 5）的元素替换为 1，操作代价为 5-2+1=4。操作后数组变为 [1, 1, 1, 1, 1, 1]，所有元素相等，且此代价为最小可能。