Настя испекла \(m\) блинов и разложила по \(n\) тарелкам. Тарелки стоят в одном ряду и пронумерованы слева направо. На тарелку с номером \(i\) она положила \(a_i\) блинчиков.
Увидев тарелки, Влад решил привнести порядок в стопки и переложить некоторые блинчики. За один ход он может переложить один блинчик с любой тарелки на соседнюю, то есть выбрать тарелку \(i\) (\(a_i > 0\)) и сделать одно из следующих действий:
- при \(i > 1\) переложить блинчик на тарелку с предыдущим индексом, после такого действия \(a_i = a_i - 1\) и \(a_{i - 1} = a_{i - 1} + 1\);
- при \(i < n\) переложить блинчик на тарелку со следующим индексом, после такого действия \(a_i = a_i - 1\) и \(a_{i + 1} = a_{i + 1} + 1\).
Влад хочет сделать массив \(a\) невозрастающим, переложив при этом как можно меньше блинчиков. Помогите ему найти минимальное количество перекладываний, необходимых для этого.
Массив \(a=[a_1, a_2,\dots,a_n]\) называется невозрастающим, если \(a_i \ge a_{i+1}\) для всех \(i\) от \(1\) до \(n-1\).
Выходные данные
Выведите единственное число — минимальное количество перекладываний, необходимое чтобы сделать массив \(a\) невозрастающим.
Примечание
В первом примере нужно сначала переложить блинчик с тарелки \(1\), после чего \(a = [4, 4, 2, 3, 3, 3]\). После необходимо переложить блинчик с тарелки \(2\) на тарелку \(3\) и массив станет невозрастающим \(a = [4, 3, 3, 3, 3, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 19
5 3 2 3 3 3
|
2
|
|
2
|
3 6
3 2 1
|
0
|
|
3
|
3 6
2 1 3
|
1
|
|
4
|
6 19
3 4 3 3 5 1
|
3
|
|
5
|
10 1
0 0 0 0 0 0 0 0 0 1
|
9
|