给你一个数组 $$$a_{1}, a_{2}, \ldots, a_{n}$$$。您最多可以从中删除一个子段。其余元素应成对不同。
换句话说,最多一次可以选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) 并从数组中删除整数 $$$a_l, a_{l+1}, \ldots, a_r$$$。其余元素应成对不同。
找到需要删除的子段的最小大小,以使所有剩余元素都不同。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — 给定数组中的元素数量。
下一行包含 $$$n$$$ 间隔整数 $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \le a_{i} \le 10^{9}$$$) — 数组的元素。
输出
打印单个整数 - 您需要删除的子段的最小大小,以使数组的所有元素成对不同。如果不需要删除任何子段,则打印$$$0$$$。
示例
输入 #1
3 1 2 3
输出 #1
0
输入 #2
4 1 1 2 2
输出 #2
2
输入 #3
5 1 4 1 4 9
输出 #3
2
注意
在第一个示例中,所有元素都已经不同,因此不需要删除任何子段。
在第二个示例中,您可以删除索引 $$$2$$$ 到 $$$3$$$ 的子段。
在第三个示例中,您可以删除索引 $$$1$$$ 到 $$$2$$$、索引 $$$2$$$ 到 $$$3$$$ 或索引 $$$3$$$ 到 $$$4$$$ 的子段。