Вычислительная ихтиология
(Время: 1 сек. Память: 16 Мб Сложность: 35%)
Игорь работает младшим лаборантом в НИИ ихтиологии. Ему вверены n аквариумов, стоящих в ряд, в каждом из которых живет колония рыбок гуппи. Про каждую колонию заранее известна ее численность.
В лабораторных условиях НИИ ихтиологии колония рыбок гуппи растет по следующему правилу: достигнув популяции в f рыбок, колония живет в течении max(1000−f, 1) секунд, после чего на свет появляется новая рыбка. От начального момента времени до рождения первой рыбки колония размера f также ждет max(1000−f, 1) секунд.
Например, колония с начальным размером 996 будет размножаться следующим образом:
| момент времени | размер колонии | время до очередной рыбки |
|---|
0
4
7
9
10
11
12
… |
996
997
998
999
1000
1001
1002
… |
4
3
2
1
1
1
1
… |
Появление на свет каждой новой рыбки Игорь должен фиксировать в специальном журнале. Будем считать, что запись он делает мгновенно, но при этом он должен в момент рождения новой рыбки находиться рядом с аквариумом, в котором это произошло.
На перемещение от одного аквариума к соседнему у Игоря уходит одна секунда. В начальный момент времени Игорь стоит около первого аквариума.
Вычислите, в течение какого наибольшего периода времени Игорь сможет добросовестно выполнять свою работу.
Входные данные
В первой строке входного файла INPUT.TXT содержится целое число n (2 ≤ n ≤ 50) – количество аквариумов с рыбками гуппи в НИИ ихтиологии. Каждая из следующих n строк содержит одно целое число ai (1 ≤ ai ≤ 2007) – численность i-й колонии.
Выходные данные
В выходной файл OUTPUT.TXT выведите момент времени, когда родится первая рыбка гуппи, запись о рождении которой Игорь сделать не сможет.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
996
1
994 | 7 |
Пояснение к примеру
В приведенном примере Игорь сначала ждет у первого аквариума появления рыбки на 4-й секунде. После этого он бежит к третьему аквариуму (на это у него уходит 2 секунды) и как раз успевает к рождению рыбки на 6-й секунде. Однако вернуться к первому аквариуму, где следующая рыбка родится на 7-й секунде, он уже не успевает.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
