Author : Kamonasish Roy
Tester : Md Jahirul Islam Hridoy, Abu Sufian Rafi, Abid Hussen, Emon Thakur
Editorial : To build such a permutation, we use a simple greedy and safe strategy: swap adjacent elements.

Algorithm Steps:

Start with the array:
1 2 3 4 5 ... N

Swap every pair of adjacent elements:
Swap (1,2), (3,4), (5,6), and so on.

Example:
1 2 3 4 → after swaps → 2 1 4 3

If N is odd, the last element will remain in its original position.
To fix this, swap the last two elements again.

Example for N=5:
After adjacent swaps: 2 1 4 3 5
Since 5 is still at position 5 → swap (4,5): 2 1 4 5 3

Why It Works:

Swapping adjacent elements ensures no number stays in the same place.

It gives the smallest possible values at the earliest positions → making the permutation lexicographically smallest.

Time Complexity: O(N).

Code ( C++ ):

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;


        vector<int> p(n+1,0);
        for (int i = 1; i<= n; i += 1) {
            p[i] = i;
        }
        for(int i=2;i<=n;i+=2){
        	swap(p[i],p[i-1]);
        }

        if (n % 2 == 1) {
            swap(p[n ], p[n - 1]); // fix last 3 elements to avoid i == P_i
        }

        for (int i = 1; i <= n; ++i)
            cout << p[i] << ' ';
        cout << '\n';
    }
}