B. Шоколадки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы пришли в магазин, продающих $$$n$$$ типов шоколадок. Всего в наличии есть $$$a_i$$$ шоколадок типа $$$i$$$.

У вас есть неограниченное количество денег (так что никаие цены не являются ограничивающим фактором) и вы хотите купить как можно больше шоколадок. Однако, если вы купите $$$x_i$$$ шоколадок типа $$$i$$$ (очевидно, $$$0 \le x_i \le a_i$$$), то для каждого $$$1 \le j < i$$$ должно быть верно хотя бы одно из двух:

  • $$$x_j = 0$$$ (вы купили ноль шоколадок типа $$$j$$$)
  • $$$x_j < x_i$$$ (вы купили меньше шоколадок типа $$$j$$$, чем типа $$$i$$$)

Например, массив $$$x = [0, 0, 1, 2, 10]$$$ удовлетворяет условию выше (в предположении, что все $$$a_i \ge x_i$$$), а массивы $$$x = [0, 1, 0]$$$, $$$x = [5, 5]$$$ и $$$x = [3, 2]$$$ нет.

Вычислите наибольшое количество шоколадок, которое вы можете купить.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество типов шоколадок.

Следующая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — количество шоколадок каждого вида.

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

Выведите максимальное количество шоколадок, которое можно купить.

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

В первом примере оптимально купить: $$$0 + 0 + 1 + 3 + 6$$$ шоколадок.

Во втором примере оптимально купить: $$$1 + 2 + 3 + 4 + 10$$$ шоколадок.

В третьем примере оптимально купить: $$$0 + 0 + 0 + 1$$$ шоколадок.