B3. Военные учения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Умный Бобер из ABBYY начал сотрудничество с министерством обороны. Сейчас проводятся учения по передвижению танковых колонн. На этих учениях тестируется новый вид танков, имеющих возможность передавать информацию. Для тестирования нового вида танков на учениях проводится специальное упражнение, суть которого заключается в следующем.

Изначально колонна состоит из n танков, последовательно пронумерованных от 1 до n в порядке от начала колонны к ее концу. За все упражнение нужно передать ровно n сообщений из начала колонны в её конец.

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

После получения сообщения последний танк (с номером n) переезжает в начало колонны и аналогичным образом передаёт другое сообщение в конец колонны. Когда сообщение доходит до последнего танка (с номером n - 1), этот танк переезжает в начало и передаёт следующее сообщение в конец колонны, и так далее. Таким образом, упражнение завершается, когда колонна приобретает исходный вид, то есть сразу после перемещения танка номер 1 в начало колонны.

Если изначально танки в колонне располагались в порядке 1, 2, ..., n, то после первого переезда они будут располагаться в порядке n, 1, ..., n - 1, после второго переезда — в порядке n - 1, n, 1, ..., n - 2, и так далее.

Устройство танков является весьма специфичным. Танк с номером i характеризуется одним целым числом ai, которое называется радиусом приема сообщений этого танка.

Передача сообщения между двумя танками занимает одну секунду, при этом не всегда один танк может передать сообщение другому. Рассмотрим два танка в колонне такие, что первый из них является i-ым по счёту с начала колонны, а второй — j-ым по счёту, причём второй танк имеет номер x. Тогда первый танк может передать второму танку сообщение, если i < j и i ≥ j - ax.

Перед министерством обороны (а вскоре и перед Умным Бобром) встал вопрос об эффективной организации учений — нужно провести упражнение за минимальное время. Временем перемещения танков в колонне будем пренебрегать, так как улучшение скоростных характеристик танков не является приоритетной задачей на этих учениях.

Вам дано количество танков, а также радиусы приёма сообщений всех танков. Вы должны помочь Умному Бобру и организовать передачу сообщений таким образом, чтобы суммарное время передачи всех сообщений было минимально возможным.

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

Первая строка содержит целое число n — количество танков в колонне. Следующие n строк содержат по одному целому числу ai (1 ≤ ai ≤ 250000, 1 ≤ i ≤ n) — радиусы приема сообщений танков в порядке от танка с номером 1 к танку с номером n (напомним, что изначально танки расположены в колонне по порядку номеров).

Для получения полного балла за первую группу тестов достаточно решить задачу при 2 ≤ n ≤ 300.

Для получения полного балла за вторую группу тестов достаточно решить задачу при 2 ≤ n ≤ 10000.

Для получения полного балла за третью группу тестов достаточно решить задачу при 2 ≤ n ≤ 250000.

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

Выведите одно целое число — минимально возможное суммарное время передачи сообщений.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3
2
1
1
Выходные данные
5
Входные данные
5
2
2
2
2
2
Выходные данные
10
Примечание

В первом примере изначальный порядок танков — 1, 2, 3. Первый танк передает сообщение второму, затем второй передает третьему — это занимает две секунды. Третий танк переезжает вперед и порядок танков теперь 3, 1, 2. Третий танк передает сообщение первому, затем первый передает второму — это занимает еще две секунды. Второй танк переезжает вперед и порядок танков теперь 2, 3, 1. При таком расположении второй танк сразу может передать сообщение первому, поскольку радиус приема первого танка достаточен — это занимает одну секунду. Наконец, танки возвращаются в исходный порядок 1, 2, 3. Всего упражнение занимает 5 секунд.

Во втором примере все пять танков одинаковы и передача одного сообщения занимает две секунды, поэтому всего упражнение занимает 10 секунд.