# B. Perfecto (Round 1007 Div.2)

Link đề : https://codeforces.com/contest/2071/problems
## Đề bài

- **Nội dung** : Cho $1$ số nguyên dương $n$. Bạn cần sắp xếp các số từ $1$ đến $n$ thành $1$ hoán vị (tức là dãy gồm $n$ chữ số, mỗi số từ $1$ đến $n$ xuất hiện đúng $1$ lần) sao cho với mọi chỉ số $i$ (từ 1 đến $n$) tổng của $i$ phần tử đầu tiên
$$
S_i = p_1 + p_2 + \dots + p_i
$$
không là 1 số chính phương. Nếu không có hoán vị nào thỏa mãn ta in ra $-1$.
- **Ví dụ** :
- $n = 1$ : Ta có 1 hoán vị duy nhất là [ $1$ ], nhưng vì 1 là số chính phương nên không thỏa mãn điều kiện
- $n = 4$ : Ta có 1 hoán vị hợp lệ là [ $2, 4, 1, 3$ ] vì các tổng tiền tố là
- $2$ (không là số chính phương)
- $2 + 4 = 6$
- $2 + 4 + 1 = 7$
- $2 + 4 + 1 + 3 = 10$

## Phân tích
#### Tổng của cả dãy số
Với bất kì cách sắp xếp nào, ta có tổng toàn bộ dãy số từ $1$ đến $n$ luôn bằng
$$
S_n = 1 + 2 + \dots + n = \frac{n(n+1)}{2}.
$$
Nếu $S_n$ lại là số chính phương, thì dù ta sắp xếp theo cách nào, tổng của cả dãy (là tổng tiền tố cuối cùng) vẫn là một số chính phương. Khi đó, không có hoán vị nào thỏa mãn yêu cầu của đề bài.
Nên ta có **nhận xét** đầu tiên :
$$
S_n = \frac{n(n+1)}{2}
$$
là số chính phương thì đáp án là $-1$
#### Điều kiện để hoán vị thỏa mãn
Với mỗi vị trí $i$ (từ $1$ đến $n$), tổng tiền tố $S_i$ phải không là số chính phương. Khi đó ta cần kiểm tra mọi tổng tiền tố của hoán vị

## Ý tưởng
Giả sử tổng $S_n$ không phải là số chính phương, ta luôn có cách sắp xếp sao cho mọi tiền tố đều thỏa mãn điều kiện. Ý tưởng như sau

#### 1. Bắt đầu với hoãn vị của [ $1, 2, 3, \dots, n$ ]
Sử dụng hoán vị ban đầu là dãy [ $1, 2, 3, \dots, n$ ]. Ta tính các tổng tiền tố
- $S_1 = 1$
- $S_2 = 1 + 2 = 3$
- $S_3 = 1 + 2 + 3 = 6$
- $\dots$
#### 2. Kiểm tra từng tổng tiền tố
Duyệt qua các chỉ số từ $1$ đến $n$
- Nếu tổng $S_i$ không là số chính phương thì ta giữ nguyên
- Nếu không Ta thức hiện hoán vị giữa phần tử thứ $i$ và phần tử thứ $i + 1$

#### 3. Vì sao lại hoán vị như vậy
Ta xét
$$
S_k = p_1 + p_2 + \dots + p_k
$$

là số chính phương, ta đổi vị trí của $p_k$ và $p_{k+1}$
Tổng tiền tố mới đến vị trí k trở thành
$$
S'_k = (S_k - p_k) + p_{k+1} = S_k - k + (k+1) = S_k + 1.
$$
Vì hiệu giữa các số chính phương liên tiếp (ví dụ $x^2$ và ${(x + 1)}^2$) luôn lớn hơn 1 cụ thể
$$
{(x + 1)}^2 - x^2 = 2x + 1
$$
với $x \ge 1$, nên $S'_k$ chắc chắn không là số chính phương
#### 4. Chứng minh
Giả sử sau khi đổi vị trí giữa $p_k$ và $p_{k + 1}$ vẫn là số chính phương
Đặt $S_k = x^2$ khi đó $S'_k = x^2 + 1$
Mà $S'_k$ cũng là số chính phương nên

$S'_k = y^2 = x^2 + 1$
$\Leftrightarrow y^2 = x^2 + 1$
$\Leftrightarrow y^2 - x^2 = 1$
$\Leftrightarrow (y - x)(y + x) = 1$

Mặt khác $x \ge 1$ và $y > x$ (vì $y^2 = x^2 + 1$) nên ta có
- $y - x \ge 1$
- $y + x \ge 2x + 1 \ge 3$ (với $x \ge 1$)

$\Rightarrow (y - x)(y + x) \ge 3 > 1$ (Vô lý)
Do đó $S'_k$ không thể là số chính phương

## Code mẫu
Độ phức tạp $O(t*n)$

/*
* Language: Standard C++20 [-std=c++20]
* Codeforces : @zvwg.vx
*/

#pragma GCC optimize("fast-math,O3")
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("tune=native")
// #pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

#if LOCAL
#include <algo/debug.h>
#endif

using namespace std;

#define el cout << '\n'
#define rt return
#define ll long long
#define ull unsigned long long
#define vec vector
#define bs bitset
#define ust unordered_set
#define ump unordered_map
#define priq priority_queue

template <typename T> T lcm(T a, T b) { rt a * (b / __gcd(a, b)); }
template <typename T> double lg(T a, T b) { rt log(b) / log(a); }
template <typename T> void maximize(T& a, T b) { if (a < b) a = b; }
template <typename T> void minimize(T& a, T b) { if (a > b) a = b; }
template <typename T> ull P(T n, T k) { ull res = 1; for (int i = 0; i < k; i++) res *= (n - i); rt res; }
template <typename T> ull C(T n, T k) { ull res = 1; for (int i = 1; i <= k; i++) res = res * (n - i + 1) / i; rt res; }

const int limit = 1e6;
const int infi = 1e9;
const int mod = 1e9 + 7;

void open_file(const string& file) {
    if (file == "-1") rt;
    freopen((file + ".inp").c_str(), "r", stdin);
    freopen((file + ".out").c_str(), "w", stdout);
}


signed main() { 
    cin.tie(nullptr), cout.tie(nullptr)
    -> ios_base::sync_with_stdio(false);

    #ifndef ONLINE_JUDGE
    srand(time(nullptr));
    open_file("sol");
    #endif

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        
        ll sum = (ll)(n * (n + 1) >> 1);
        ll sqr = sqrt(sum);

        if (sqr * sqr == sum) {
            cout << -1;
        } else {
            vec<int> res(n + 1, 0);
            for (int i = 1; i <= n; ++i) res[i] = i;

            int j = 0;
            for (int i = 1; i <= n; ++i) {
                while ((ll)j * j < ((ll)i * (i + 1) >> 1)) ++j;

                if ((ll)(j * j) == (ll)(i * (i + 1) >> 1)) {
                    swap(res[i], res[i + 1]);
                }

                cout << res[i] << ' ';
            }
        }   
        el;
    }

    el;
    rt 0;   
}