Задача №113349. Турнир по DOTY

Совсем недавно закончился межгалактический турнир по известной онлайн-игре «Defence of the Young». Во время турнира страсти разыгрались не на шутку, и судьи только и успевали, что планировать проведение матчей и следить за соблюдением правил. К несчастью, ни одна команда из галактики Млечный путь не смогла пройти отбор на соревнования, поэтому мы традиционно болели за наших друзей из скопления Андромеды.

Всего в соревнованиях участвовало n команд. Турнир проводился по олимпийской системе, то есть команда выбывала сразу после первого проигрыша. Поскольку на турнире присутствовали команды с самым разным уровнем мастерства, то сетка турнира могла быть совершенно произвольной. В частности, количество участвовавших команд совершенно не обязательно было равно какой-либо степени двойки. Также известно, что никакая команда не играла две игры в один день.

К сожалению, во время бурного чествования ставшей победителем команды «Kind Genius», были утеряны записи о самом турнире. Единственная информация, которую смогло найти жюри, это количество матчей, сыгранное в каждый из дней турнира. Жюри просит вас, пользуясь этими данными и информацией о структуре турнира из предыдущего абзаца, восстановить хотя бы значение n — количество команд, участвоваших в турнире.

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

В первой строке входных данных записано целое число k ( 1 ≤ k ≤ 100 000 ) –– количество дней, которое длился межгалактический турнир по DOTY. В следующей строке записаны k неотрицательных целых чисел, не превышающих 10 9 , i -е из них задаёт количество игр, сыгранных в i -й день турнира.

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

Выведите единственное целое число n — количество команд, участвовавших в турнире. Гарантируется, что n может быть однозначно восстановлено по входным данным и будет не больше 10 9 . Также гарантируется, что в турнире участвовала хотя бы одна команда.

Примечание

Одной из возможных сеток турнира во втором примере является:

  1. Первая и вторая команда играют матч в первый день.
  2. Победитель первого матча играет с третьей командой во второй день.
  3. Победитель второго матча играет в финале с четвёртой командой в третий день соревнований.
Примеры
Входные данные
3
2 2 1
Выходные данные
6
Входные данные
5
0 1 0 1 1
Выходные данные
4
Сдать: для сдачи задач необходимо войти в систему