J. Кольцевая задача
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
128 мегабайт
ввод
input.txt
вывод
output.txt
Нас ждут бездны открытий и мудрости.
Константин Циолковский

Профессор X заботился о безопасности в любом вопросе. Поэтому при подготовке полета на Марс он также поднял тему безопасности. В частности, его внимание привлекли скафандры, которые космонавты будут надевать для выхода на поверхность планеты.

По распоряжению профессора X каждый скафандр должен быть экипирован специальной системой, которая в случае непредвиденных обстоятельств послужит хорошей страховкой космонавту. Эта система состоит из наногенератора плазменных колец, вскрывателя, закрывателя и соединителя. В случае опасности космонавт может нажать специальную кнопочку на своем скафандре, и система активируется.

Работает эта система следующим образом: сначала наногенератор создаст $$$n$$$ цепей из сверхпрочных плазменных колец, которые в дальнейшем соединятся в единую цепь и пристыкуются к кораблю «Запад-1». Чтобы соединить 2 цепи между собой, должен сначала активироваться вскрыватель, который вскрывает какое-нибудь кольцо на какой-либо цепи и отсоединяет его от этой цепи. Затем в дело вступает соединитель, который притягивает два конца каких-либо цепей в только что открытое кольцо. А потом закрыватель закрывает вскрытое кольцо.

Вся соль этой системы в том, что количество колец в цепях, созданных наногенератором, может быть разным для разных цепей. Поэтому профессор X попросил Вас написать для системы безопасности еще один модуль, который будет вскрывать и закрывать наименьшее число колец, ведь на вскрытие и закрытие тратится очень много энергии.

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

В единственной строке входного файла содержится единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество цепей, сгенерированных наногенератором.

В следующей строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — количество колец в $$$i$$$-й цепи.

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

В единственной строке выходного файла должно быть записано единственное целое число — наименьшее количество колец, которые надо вскрыть и закрыть для того, чтобы можно было образовать единую цепь.

Примеры
Входные данные
5
3 3 3 3 3
Выходные данные
3
Входные данные
3
1 6666 100500
Выходные данные
1