Поликарпу подарили некоторую последовательность целых чисел \(a\) длины \(n\) (\(1 \le a_i \le n\)). Последовательность может порадовать Поликарпа, только если она состоит из различных чисел. Для того чтобы сделать свою последовательность такой, Поликарп собирается сделать некоторое (возможно, нулевое) количество ходов.
За один ход он может:
- удалить первый (крайний левый) элемент последовательности.
Например, за один ход из последовательности \([3, 1, 4, 3]\) получится последовательность \([1, 4, 3]\), которая состоит из различных чисел.
Определите, какое минимальное количество ходов ему надо сделать, чтобы в оставшейся последовательности все элементы были различны. Иными словами, найдите длину наименьшего префикса заданной последовательности \(a\), после удаления которого все значения в последовательности будут уникальны.
Выходные данные
Для каждого набора входных данных выведите ответ на отдельной строке — минимальное количество элементов, которые надо удалить из начала последовательности, чтобы все оставшиеся элементы оказались различны.
Примечание
Ниже перечислены последовательности, которые останутся после удаления префиксов:
- \([1, 4, 3]\);
- \([1]\);
- \([1]\);
- \([6, 5, 4, 3, 2, 1]\);
- \([2, 1]\).
Легко увидеть, что все оставшиеся последовательности содержат только различные элементы. В каждом наборе входных данных был удалён самый короткий из подходящих префиксов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
3 1 4 3
5
1 1 1 1 1
1
1
6
6 5 4 3 2 1
7
1 2 1 7 1 2 1
|
1
4
0
0
5
|