An array is sorted if it has no inversions
A Young Boy
Вам дан массив из \(n\) целых положительных чисел \(a_1,a_2,\ldots,a_n\).
За одну операцию вы можете выполнить следующие действия:
- Выбрать любое число \(x\).
- Для всех \(i\) таких, что \(a_i = x\), выполнить \(a_i := 0\) (присвоить \(0\) значению \(a_i\)).
Найдите минимальное количество операций, необходимых для того, что отсортировать массив в неубывающем порядке.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество операций, необходимых для того, чтобы отсортировать массив в неубывающем порядке.
Примечание
В первом наборе входных данных вы можете выбрать \(x = 3\) при применении операции, тогда итоговый массив будет равен \([0, 0, 2]\).
Во втором наборе входных данных, вы можете выбрать \(x = 1\) при применении первой операции и \(x = 3\) при применении второй операции, тогда итоговый массив будет равен \([0, 0, 0, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1
|
1
2
4
3
0
|