Дан массив $$$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$$$.
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$$$.
Название |
---|