Олимпиадный тренинг

Задача . B. Красота картин


На выставку были привезены n картин. Каждая картина имеет красоту ai. Известно, что посетитель выставки всегда радуется, когда при движении вдоль ряда картин следующая картина красивее предыдущей.

Какое максимальное количество раз может порадоваться посетитель при оптимальном порядке расположения картин на стене? Иными словами, расставьте элементы последовательности a таким образом, чтобы максимизировать количество i (1 ≤ i ≤ n - 1), таких что ai + 1 > ai.

Входные данные

В первой строке входных данных следует число n (1 ≤ n ≤ 1000) — количество картин.

Во второй строке входных данных следует последовательность из n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1000), где ai означает красоту i-й картины.

Выходные данные

Выведите единственное целое число — максимальное количество пар соседних картин таких, что 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
Статистика успешных решений по компиляторам
 Кол-во
С++5