← 返回题目列表

Codeforces · 1208/B

B. 独特性

中文机器翻译题面 查看原题

给你一个数组 $$$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$$$ 的子段。