Вы пришли в магазин, продающих \(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]\) нет.
Вычислите наибольшое количество шоколадок, которое вы можете купить.
Примечание
В первом примере оптимально купить: \(0 + 0 + 1 + 3 + 6\) шоколадок.
Во втором примере оптимально купить: \(1 + 2 + 3 + 4 + 10\) шоколадок.
В третьем примере оптимально купить: \(0 + 0 + 0 + 1\) шоколадок.