На выставку были привезены n картин. Каждая картина имеет красоту ai. Известно, что посетитель выставки всегда радуется, когда при движении вдоль ряда картин следующая картина красивее предыдущей.
Какое максимальное количество раз может порадоваться посетитель при оптимальном порядке расположения картин на стене? Иными словами, расставьте элементы последовательности a таким образом, чтобы максимизировать количество i (1 ≤ i ≤ n - 1), таких что ai + 1 > ai.
Выходные данные
Выведите единственное целое число — максимальное количество пар соседних картин таких, что ai + 1 > ai, после оптимального переупорядочивания последовательности a.
Примечание
В первом примере оптимальный порядок расположить картины: 10, 20, 30, 40, 50.
В втором примере оптимальный порядок расположить картины: 100, 200, 100, 200.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
20 30 10 50 40
|
4
|
|
2
|
4
200 100 100 200
|
2
|