Профессор 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
| Name |
|---|


