Великий фараон Флатландии недавно взошёл на престол и озаботился вопросом строительства пирамиды для себя.
Флатландия — двумерная страна, у неё есть только длина и высота. Для строительства пирамиды был выделен участок длиной в N стандартных блоков. Каждый единичный отрезок был обследована геологами, которые выяснили количество стандартных блоков 1 на 1, которые могут быть уложены в столбик на эту клетку без угрозы проседания грунта.
Пирамидой называется фигура, состоящая из блоков 1 на 1, такая, что каждый горизонтальный слой представляет собой непрерывный отрезок. Под каждым блоком должен находится блок предыдущего слоя или земля (в нижнем слое). Количество блоков в каждом столбце не должно превосходить грузоподъёмности клетки, на которой находится этот столбец.
Фараон хочет, чтобы его пирамида состояла из как можно большего числа блоков. Помогите ему определить это число.
Формат входных данных
В первой строке входных данных задано целое число N (1 ≤ N ≤ 300000) — длина участка,
выделенного для строительства пирамиды.
Во второй строке задано N целых чисел Wi (0 ≤ Wi ≤ 10
9) — грузоподъемности отрезков
единичной длины.
Формат выходных данных
Выведите максимальное количество блоков, из которого может быть построена пирамида.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
7 0 1 3 2 3 |
8 |