Областная олимпиада по информатике 2013-2014

Многие математические игры кажутся довольно странными для посторонних. Вот пример одной из них.
У вас имеется 2N − 1 карточек. Вначале в игре участвуют N карточек. На лицевой стороне каждой из них написано какое-то целое число. На обратной стороне этих же карточек написан 0 (ноль). Остальные N −1 карточек пустые с обеих сторон и пока не участвуют в игре. Вы загадываете какое-то число от 1 до N. Каждый ход игры игры заключается в следующих действиях:

• выбрать карточку с наименьшим числом на лицевой стороне. Если таких карточек несколько — выбрать ту, на обратной стороне которой число минимально. Пусть выбрана карточка с числом A на лицевой стороне и B на обратной стороне. Убрать эту карточку из игры.
• еще раз выбрать карточку с наименьшим числом на лицевой стороне. Если таких карточек несколько — выбрать ту, на обратной стороне которой число минимально. Пусть выбрана карточка с числом C на лицевой стороне и D на обратной стороне. Убрать эту карточку из игры.
• взять пустую карточку. На лицевой стороне написать число, равное A + C, а на обратной — максимальное из чисел B + 1 и D + 1. Добавить эту карточку в игру.

Игра заканчивается через N − 1 ход, когда в игре останется только одна карточка. Если число, которое вы загадали в начале, совпадает с числом, которое написано на обратной стороне оставшейся карточки, то вы выиграли. Иначе — вы проиграли.
Напишите программу, которая по исходному состоянию игры определяет число, которое будет написано на обратной стороне последней карточки.

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

Первая строка входного файла содержит число $N$ ($1 ≤ N ≤ 10^5$). Следующая строка содержит $N$ целых чисел — числа, написанные на лицевой стороне карточек. Каждое число лежит в промежутке от $−10^9$ до $10^9$ включительно.

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

Выведите одно целое число — ответ к задаче.

Примеры:

Вход:

5 
1 2 3 4 5

Ответ:

3

Примечание:

Описание ходов игры: исходное состояние: (1 0), (2 0), (3 0), (4 0), (5 0) после хода 1: (3 1), (3 0), (4 0), (5 0)
после хода 2: (6 2), (4 0), (5 0)
после хода 3: (6 2), (9, 1)
после хода 4: (15, 3)
В 50% тестов $N ≤ 1000$.