Вам дано масив цілих чисел довжиною та ціле число . Ви можете виконувати наступну операцію:
Оберіть будь-яке таке, що 1 \leq i \leq n, і встановіть a_i = x.
Знайдіть найменшу кількість операцій, яку вам потрібно виконати, щоб зробити масив неспадним. Масив довжиною називається неспадним, якщо 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.
Example
Для першого тестового набору нижче наведено оптимальні операції для 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] замінивши останні три елементи на .