Задача №3407. Вычислительная ихтиология
Игорь работает младшим лаборантом в НИИ ихтиологии. Ему вверены \(n\) аквариумов, стоящих в ряд, в каждом из которых живет колония рыбок гуппи. Про каждую колонию заранее известна ее численность.
В лабораторных условиях НИИ ихтиологии колония рыбок гуппи растет по следующему правилу: достигнув популяции в \(f\) рыбок, колония живет в течении \(max(1000 - f, 1)\) секунд, после чего на свет появляется новая рыбка. От начального момента времени до рождения первой рыбки колония размера \(f\) также ждет \(max(1000 - f, 1)\) секунд.
Например, колония с начальным размером 996 будет размножаться следующим образом:
| момент времени | размер колонии | время до очередной рыбки |
|---|---|---|
| 0 | 996 | 4 |
| 4 | 997 | 3 |
| 7 | 998 | 2 |
| 9 | 999 | 1 |
| 10 | 1000 | 1 |
| 11 | 1001 | 1 |
| 12 | 1002 | 1 |
| ... | ... | ... |
Появление на свет каждой новой рыбки Игорь должен фиксировать в специальном журнале. Будем считать, что запись он делает мгновенно, но при этом он должен в момент рождения новой рыбки находиться рядом с аквариумом, в котором это произошло.
На перемещение от одного аквариума к соседнему у Игоря уходит одна секунда. В начальный момент времени Игорь стоит около первого аквариума.
Вычислите, в течение какого наибольшего периода времени Игорь сможет добросовестно выполнять свою работу.
В первой строке входного файла содержится целое число \(n\) (\(2 \le n \le 50\)) - количество аквариумов с рыбками гуппи в НИИ ихтиологии. Каждая из следующих \(n\) строк содержит одно целое число \(a_i\) (\(1 \le a_i \le 2007\)) - численность \(i\)-й колонии.
В выходной файл выведите момент времени, когда родится первая рыбка гуппи, запись о рождении которой Игорь сделать не сможет.
В приведенном примере Игорь сначала ждет у первого аквариума появления рыбки на 4-й секунде. После этого он бежит к третьему аквариуму (на это у него уходит 2 секунды) и как раз успевает к рождению рыбки на 6-й секунде. Однако вернуться к первому аквариуму, где следующая рыбка родится на 7-й секунде, он уже не успевает.
3 996 1 994
7