Сума проти MEX#13063

Сума проти MEX

2 секунди

256 мегабайтів

Вам задано ціле число $n$ . Перестановка $p$ з $n$ елементів називається хорошою, якщо виконується така умова:

для кожного індексу $i$ ( $1 \leq i \leq n$ 1 \le i \le n) : $j = 1 \sum i p_{j}$ \sum\limits_{j=1}^{i} p_j ділиться на $MEX$ $(p_{1}, p_{2}, \dots, p_{i})$ (p_1 , p_2 , \ldots, p_i).

де $MEX$ — це найменше додатне ціле число, якого немає в масиві максимізуйте перестановку за допомогою певного процесу, схожого на мемоїзацію.

Знайдіть хорошу перестановку з $n$ елементів або повідомте, що це неможливо.

Вхідні дані

Перший рядок містить одне ціле число $t$ ( $1 \leq t \leq 700$ 1 \le t \le 700)— кількість тестових випадків.

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

Гарантується, що сума $n$ за всіма тестовими випадками не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть $"YES"$ , якщо хороша перестановка існує, а потім виведіть хорошу перестановку $p$ з $n$ елементів, або виведіть $"NO"$ , якщо хорошої перестановки не існує.

Приклади

Приклад 1

Примітка

У третьому тестовому випадку підходить $p = [3, 1, 4, 2]$ p = [3,1,4,2], оскільки

Коли $i = 1$ i = 1 , $p_{1} = 3$ p_1 = 3 , $MEX (3) = 1$ \text{MEX}(3) = 1 і $3 mod 1 = 0$ 3 \bmod 1= 0 , отже, умова виконується.
Коли $i = 2$ i = 2 , $p_{1} + p_{2} = 4$ p_1 + p_2 = 4 , $MEX (3, 1) = 2$ \text{MEX}(3 , 1) = 2 і $4 mod 2 = 0$ 4 \bmod 2=0 , отже, умова виконується.
Коли $i = 3$ i = 3 , $p_{1} + p_{2} + p_{3} = 8$ p_1 + p_2 + p_3 = 8 , $MEX (3, 1, 4) = 2$ \text{MEX}(3 , 1 , 4) = 2 і $8 mod 2 = 0$ 8 \bmod 2=0 , отже, умова виконується.
Коли $i = 4$ i = 4 , $p_{1} + p_{2} + p_{3} + p_{4} = 10$ p_1 + p_2 + p_3 + p_4 = 10 , $MEX (3, 1, 4, 2) = 5$ \text{MEX}(3,1,4,2) = 5 і $10 mod 5 = 0$ 10 \bmod 5=0 , отже, умова виконується.

Отже, ця перестановка є коректною конструкцією.

Оцінювання

Підзадача $1$ ( $25$ балів): $\sum n \leq 10$ \sum n \le 10.
Підзадача $2$ ( $50$ балів): Без додаткових обмежень.