Милена получила массив целых чисел \(a_1, a_2, \ldots, a_n\) длины \(n\) от тайного поклонника. Она думает, что сделав этот массив неубывающим, она сможет узнать личность тайного поклонника.
Она может использовать следующую операцию, чтобы сделать этот массив неубывающим.
- Выбрать элемент \(a_i\) массива \(a\) и целое число \(x\) такое, что \(1 \le x < a_i\). После этого заменить \(a_i\) в массиве \(a\) на два числа \(x\) и \(a_i - x\). Новые элементы (\(x\) и \(a_i - x\)) записываются в массив \(a\) вместо элемента \(a_i\) именно в таком порядке.
Более формально, пусть массив \(a\) равен \(a_1, a_2, \ldots, a_i, \ldots, a_k\) перед операцией. После операции он становится равным \(a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k\). Обратите внимание, что на каждой операции длина массива \(a\) увеличивается на \(1\).
Милена может выполнить эту операцию несколько раз (возможно, ноль). Она хочет, чтобы вы нашли минимальное количество раз, которое нужно выполнить эту операцию, чтобы сделать массив \(a\) неубывающим.
Массив \(x_1, x_2, \ldots, x_k\) длины \(k\) называется неубывающим, если \(x_i \le x_{i+1}\) для всех \(1 \le i < k\).
Выходные данные
Для каждого набора входных данных выведите одно число: минимальное количество операций, необходимое для того, чтобы сделать массив неубывающим.
Можно показать, что массив \(a\) всегда можно сделать неубывающим за конечное число операций.
Примечание
В первом наборе входных данных Милена может заменить второй элемент массива \(a\) на числа \(1\) и \(2\), в результате чего массив станет равен \([\, 1, \, \underline{1}, \, \underline{2}, \, 2 \,]\). Достаточно \(1\) операции.
Во втором наборе входных данных массив \(a\) уже неубывающий, поэтому ответ \(0\).
В третьем наборе входных данных Милена может сделать массив \(a\) неубывающим за \(3\) операции следующим образом:
- Выбрать \(i=1\) и \(x=2\) и заменить \(a_1\) на \(2\) и \(1\). Массив \(a\) становится равным \([\, \underline{2}, \, \underline{1}, \, 2, \, 1 \, ]\).
- Выбрать \(i=3\) и \(x=1\) и заменить \(a_3\) на \(1\) и \(1\). Массив \(a\) становится равным \([\, 2, \, 1, \, \underline{1}, \, \underline{1}, \, 1 \,]\).
- Выбрать \(i=1\) и \(x=1\) и заменить \(a_1\) на \(2\) и \(1\). Массив \(a\) становится равным \([\, \underline{1}, \, \underline{1}, \, 1, \, 1, \, 1, \, 1 \,]\).
Можно показать, что это невозможно сделать за \(2\) или менее операции, поэтому ответ \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 3 2
4
1 2 3 4
3
3 2 1
7
1 4 4 3 5 7 6
|
1
0
3
9
|