Задан целочисленный массив \(a\) размера \(n\). Подмассивом массива \(a\) назовем его непрерывную подпоследовательность (то есть массив \([a_l, a_{l+1}, \dots, a_r]\) для некоторых \(l\) и \(r\), удовлетворяющих условию \(1 \le l < r \le n\)). Назовем подмассив уникальным, если в нем есть целое число, которое встречается ровно один раз.
Вы можете выполнять следующую операцию любое количество раз (возможно, ни разу): выберите элемент массива и замените его любым целым числом.
Ваша задача — посчитать минимальное количество вышеописанных операций, чтобы все подмассивы массива \(a\) стали уникальными.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество вышеописанных операций, чтобы все подмассивы массива \(a\) стали уникальными.
Примечание
Во втором наборе входных данных можно заменить \(1\)-й и \(3\)-й элемент, например, следующим образом: \([3, 4, 1, 4]\).
В третьем наборе входных данных можно заменить \(4\)-й элемент, например, следующим образом: \([3, 1, 2, 3, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
2 1 2
4
4 4 4 4
5
3 1 2 1 2
5
1 3 2 1 2
|
0
2
1
0
|