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

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

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

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

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

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

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

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

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