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

Милена получила массив целых чисел $$$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$$$.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано одно число $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — длина массива $$$a$$$.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно число: минимальное количество операций, необходимое для того, чтобы сделать массив неубывающим.

Можно показать, что массив $$$a$$$ всегда можно сделать неубывающим за конечное число операций.

Пример
Входные данные
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
Примечание

В первом наборе входных данных Милена может заменить второй элемент массива $$$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$$$.