ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1818. Честные рыбаки

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Рыбаки поймали много рыб и, конечно, выпили. Наутро пришла пора делить улов. Первый проснувшийся рыбак понял, что для того чтобы поделить рыб поровну, нужно выбросить a1 рыб. Так он и сделал — выбросил a1 рыб и забрал свою долю. Второй проснувшийся рыбак не знал о том, что первый рыбак уже взял свою долю. Он поступил так же, как и первый: выбросил a2 лишних рыб и забрал свою долю. Затем так же поступили и остальные рыбаки.
Зная, сколько рыб выбросил каждый рыбак, найдите минимальное возможное количество рыб, которое могли поймать рыбаки. Известно, что рыбаки поймали хотя бы одну рыбу.

Исходные данные

В первой строке записано целое число n (2 ≤ n ≤ 2000). Во второй строке записаны целые числа a1, …, an (0 ≤ ain − 1), где ai — количество рыб, выброшенных i-м рыбаком.

Результат

Выведите минимальное количество рыб, которое должны были поймать рыбаки.

Примеры

исходные данныерезультат
2
1 1
3
3
1 0 2
19
Источник задачи: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010