题目描述

让我们把一个数组 $a$ 称作美丽的数组，如果你能通过任意次数(可能是零)的下面操作使数组中的所有元素都相同的话：

• 选择一个索引 $i(2 \leq i \leq |a|-1，a_{i-1}=a_{i+1})$ ，然后将 $a_i$ 替换为 $a_{i-1}$ 。

给你一个漂亮的数组 $a_1,a_2,...,a_n$，要使数组不再美丽，至少要删除多少个元素？禁止交换元素。如果不可能这样做，那么输出 $-1$。

输入格式

第一行包含一个整数 $n(1 \leq n \leq 3 * 10^5)$。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(1 \leq a_i \leq n)$。

输出格式

输出一个整数--为了使数组 $a$ 不再美丽，你必须从数组 $a$ 中移除的最小元素数。如果不可能，那么输出 -1。

样例

样例输入 #1

3
2 2 2

样例输出 #1

-1

样例输入 #2

5
1 2 1 2 1

样例输出 #2

1

样例输入 #3

7
3 3 3 5 3 3 3

样例输出 #3

3

提示

保证输入的 $a$ 数组为美丽的数组。

样例解释: 在第一个测试案例中，不可能通过修改数组的方式使其不再美丽。无论我们从数组中删除多少数字，由相同数字组成的数组都会保持美丽。

在第二个测试案例中，你可以删除索引 $5$ 中的数字。这样得到的数组将是 $[1,2,1,2]$ 让我们看看它是否美丽。有两种操作可供选择：

• 选择 $i=2$：数组变为 $[1,1,1,2]$。不能再对其进行其他操作，而且数字也不尽相同。
• 选择 $i=3$：数组变为 $[1,2,2,2,]$。也不能对其进行更多的运算，数字仍然不完全相同。

因此，数组 $[1,2,1,2]$ 并不美观。

在第三个测试用例中，可以删除前三个元素。这样得到的数组 $[5,3,3,3]$ 并不美观。