Дан массив целых чисел \(a\) длины \(n\).
Вы можете применить следующую операцию любое количество раз (возможно, нулевое):
- Сначала выбрать натуральное \(k\) такое, что \(1 \le k \le n\), и заплатить \(k + 1\) монету.
- Потом выбрать ровно \(k\) индексов \(1 \le i_1 < i_2 < \ldots < i_k \le n\).
- После этого, для каждого \(x\) от \(1\) до \(k\), увеличить \(a_{i_x}\) на \(1\).
Найдите минимальное количество монет, необходимых для того, чтобы сделать массив \(a\) неубывающим, то есть \(a_1 \le a_2 \le \ldots \le a_n\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество монет, необходимых для того, чтобы сделать массив \(a\) неубывающим.
Примечание
В первом наборе входных данных массив \(a\) уже отсортирован, поэтому ответ ноль.
Во втором наборе входных данных оптимальная последовательность операций это:
- Выбрать \(k = 2\) и индексы \(2\) и \(5\): \([ 2, \color{red}{1}, 4, 7, \color{red}{6} ] \rightarrow [2, 2, 4, 7, 7]\). Это стоит \(3\) монеты.
Можно доказать, что невозможно сделать
\(a\) неубывающим, потратив меньше чем
\(3\) монеты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 7 9
5
2 1 4 7 6
4
1 3 2 4
1
179
9
344 12 37 60 311 613 365 328 675
|
0
3
2
0
1821
|