CF 1208B - Uniqueness

给定一个数组 a1,a2,…,an 。您最多可以从中删除一个子段。其余元素应该是成对不同的。

换句话说，您最多可以选择一次两个整数 l 和 r（1≤l≤r≤n）并从数组中删除整数 al,al+1,…,ar。其余元素应该是成对不同的。

找到您需要删除的子段的最小大小，以使所有剩余元素都不同。

输入

输入的第一行包含一个整数 n（1≤n≤2000）——给定数组中的元素数。

下一行包含 n 个间隔整数 a1,a2,…,an（1≤ai≤109）——数组的元素。

输出

打印一个整数——您需要删除的子段的最小大小，以使数组的所有元素成对不同。如果不需要删除任何子段，则打印 0。

示例

输入

3

1 2 3

输出

0

输入

4

1 1 2 2

输出

2

输入

5

1 4 1 4 9

输出

2

注意

在第一个示例中，所有元素已经不同，因此不需要删除任何子段。

在第二个示例中，您可以删除从索引 2 到 3 的子段。

在第三个示例中，您可以删除从索引 1 到 2、从索引 2 到 3 或从索引 3 到 4 的子段。

----

暴力从两端开始查询，以为这种办法会超时的。