Совсем недавно закончился межгалактический турнир по известной онлайн-игре «Defence of the Young». Во время турнира страсти разыгрались не на шутку, и судьи только и успевали, что планировать проведение матчей и следить за соблюдением правил. К несчастью, ни одна команда из галактики Млечный путь не смогла пройти отбор на соревнования, поэтому мы традиционно болели за наших друзей из скопления Андромеды.
Всего в соревнованиях участвовало n команд. Турнир проводился по олимпийской системе, то есть команда выбывала сразу после первого проигрыша. Поскольку на турнире присутствовали команды с самым разным уровнем мастерства, то сетка турнира могла быть совершенно произвольной. В частности, количество участвовавших команд совершенно не обязательно было равно какой-либо степени двойки. Также известно, что никакая команда не играла две игры в один день.
К сожалению, во время бурного чествования ставшей победителем команды «Kind Genius», были утеряны записи о самом турнире. Единственная информация, которую смогло найти жюри, это количество матчей, сыгранное в каждый из дней турнира. Жюри просит вас, пользуясь этими данными и информацией о структуре турнира из предыдущего абзаца, восстановить хотя бы значение n — количество команд, участвоваших в турнире.
В первой строке входных данных записано целое число k (1 ≤ k ≤ 100 000) –– количество дней, которое длился межгалактический турнир по DOTY. В следующей строке записаны k неотрицательных целых чисел, не превышающих 109, i-е из них задаёт количество игр, сыгранных в i-й день турнира.
Выведите единственное целое число n — количество команд, участвовавших в турнире. Гарантируется, что n может быть однозначно восстановлено по входным данным и будет не больше 109. Также гарантируется, что в турнире участвовала хотя бы одна команда.
3
2 2 1
6
5
0 1 0 1 1
4
Одной из возможных сеток турнира во втором примере является:
| Name |
|---|


