2.2. Мелкое ограбление
Вася и Петя ограбили банк. Каждый из них смог вынести по одному мешку с золотом. Вскоре грабителей поймали.
Для того, чтобы смягчить наказание, Вася, в отличии от Пети, стал помогать следователям. Он охотно сообщил украденную им сумму, но сколько взял его напарник вспомнить не смог.
Как выяснили следователи, в банке каждый мешок с золотом был промаркирован целым числом — количество золотых монет в мешке. Банк смог сообщить только количество монет, находившихся в каждом из мешков. Из показаний Васи следовало, что он взял мешок, в котором было больше всего монет, а в мешке у Пети монет было меньше. Помогите сотрудникам правоохранительных органов выяснить, какое максимальное количество монет мог вынести Петя.
Формат входных данных:
В первой строке входного файла задано целое число N (2 ≤ N ≤ 2*106) — общее количество мешков с золотом. Во второй строке задано N целых неотрицательных чисел, не превосходящих 109 — количество монет в мешках. Гарантируется, что данные непротиворечивы.
Формат выходных данных:
В выходной файл выведите максимальное количество монет, которое мог вынести Петя.
Пример
input.txt output.txt
2
109 73 73
3
16 98 64 64