Неспадний#12913

Неспадний

Вам дано масив цілих чисел довжиною та ціле число . Ви можете виконувати наступну операцію:

Знайдіть найменшу кількість операцій, яку вам потрібно виконати, щоб зробити масив неспадним. Масив довжиною називається неспадним, якщо a_1 \leq a_2 \leq \ldots \leq a_n.

Оскільки ця задача занадто проста, вирішіть її для кожного від до .

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^4)  — кількість тестових наборів. Далі слідують описи тестових наборів.

Перший рядок кожного тестового набору містить одне ціле число (1 \leq n \leq 2\cdot 10^5)  — довжину масиву.

Другий рядок кожного тестового набору містить цілих чисел a_1, a_2, \ldots, a_n (1 \leq a_i \leq n)  — елементи масиву.

Гарантується, що сума по всіх тестових наборах не перевищує 2\cdot 10^5.

Вихідні дані

Для кожного тестового набору виведіть цілих чисел  — відповіді на задачу для x = 1, 2, \ldots, n.

Приклади

Приклад

Loading
Loading

Примітка

Для першого тестового набору нижче наведено оптимальні операції для x = 1, 2, 3, 4:

  • Для x = 1: ми можемо перетворити [2, 1, 3, 2] в [1, 1, 1, 2] замінивши перший і третій елементи на .

  • Для x = 2: ми можемо перетворити [2, 1, 3, 2] в [2, 2, 2, 2] замінивши другий і третій елементи на .

  • Для x = 3: ми можемо перетворити [2, 1, 3, 2] в [2, 3, 3, 3] замінивши другий і четвертий елементи на .

  • Для x = 4: ми можемо перетворити [2, 1, 3, 2] в [2, 4, 4, 4] замінивши останні три елементи на .