Для масиву довжиною визначимо як кількість позицій 1 \le i \le n, для яких a_i = \max(a_1, a_2, \ldots, a_i). Іншими словами, — кількість префіксних максимумів в масиві .
Вам задана перестановка (p_1, p_2, \ldots, p_n) цілих чисел від до . Знайдіть будь-яку перестановку (q_1, q_2, \ldots, q_n) цілих чисел від до , для якої виконується наступна умова:
f((q_1, q_2, \ldots, q_n)) + f((p_{q_1}, p_{q_2}, \ldots, p_{q_n})) є найбільшим серед усіх перестановок (q_1, q_2, \ldots, q_n).
Якщо існує декілька таких перестановок, знайдіть будь-яку з них.
Перший рядок містить одне ціле число (1 \le t \le 10^5) — кількість тестових наборів. Далі слідує опис тестових наборів.
Перший рядок кожного тестового набору містить одне ціле число (1 \leq n \leq 2\cdot 10^5) — довжину перестановки.
Другий рядок кожного тестового набору містить цілих чисел p_1, p_2, \ldots, p_n (1 \le p_i \le n, всі p_i різні) — елементи перестановки.
Гарантується, що сума по всіх тестових наборах не перевищує 2\cdot 10^5.
Для кожного тестового набору виведіть цілих чисел q_1, q_2, \ldots, q_n (1 \le q_i \le n, всі q_i різні) — будь-яку перестановку цілих чисел від до , яка максимізує значення f((q_1, q_2, \ldots, q_n)) + f((p_{q_1}, p_{q_2}, \ldots, p_{q_n}))
Example
У першому тестовому наборі, для q = (1, 2, 3), значення дорівнює f(1, 2, 3) + f(p_1, p_2, p_3) = f(1, 2, 3) + f(1, 2, 3) = 3 + 3 = 6.
У другому тестовому наборі, для q = (1, 3, 4, 2), значення дорівнює f(1, 3, 4, 2) + f(p_1, p_3, p_4, p_2) = f(1, 3, 4, 2) + f(2, 3, 1, 4) = 3 + 3 = 6.
У третьому тестовому наборі, для q = (1, 3, 5, 4, 2), значення дорівнює f(1, 3, 5, 4, 2) + f(p_1, p_3, p_5, p_4, p_2) = f(1, 3, 5, 4, 2) + f(1, 2, 3, 4, 5) = 3 + 5 = 8.