First, consider the following problem.

You are given an integer sequence \(A=(A_1,A_2,\ldots,A_N)\) of length \(N\) consisting of \(0\)s and \(1\)s. By rearranging \(A\) appropriately, minimize the value of \(\displaystyle \sum_{i=1}^N\bigoplus_{1\le j\le i}A_j\).

Let the indices \(i\) satisfying \(A_i=1\) be \(C_1 < C_2 < \ldots < C_{|C|}\). The value of \(\displaystyle \sum_{i=1}^N\bigoplus_{1\le j\le i}A_j\) can be expressed as \(\displaystyle \sum_{i=1}^{\left\lfloor\frac{|C|+1}2\right\rfloor} (C_{2i}-C_{2i-1})\) (where \(C_{|C|+1}=N+1\)).

From this expression, we see that the minimum value of the given expression is \(\displaystyle \left\lfloor\frac{|C|+1}2\right\rfloor\), and this value can only be achieved by arranging the sequence so that a \(1\) exists immediately to the right of each odd occurrence of \(1\). (When \(|C|\) is odd, set \(A_N=1\).)

Using this fact, let us consider the original problem.

We call the value of \(\displaystyle \sum_{i=1}^N\bigoplus_{1\le j\le i}P_j\) the score of \(P\).

First, we derive a lower bound for the score of \(P\) by considering each bit independently.

Let \(X_k\) be the number of integers between \(1\) and \(N\) whose binary representation has a \(1\) in the \(2^k\) place. From the above argument, by solving the above problem independently for each bit, we obtain \(\displaystyle \sum_k 2^k\times \left\lfloor \frac{X_k+1}2\right\rfloor\) as a lower bound for the score.

In most cases, this lower bound is achievable. Specifically, a permutation \(P\) satisfying the conditions can be constructed by the following procedure:

• Set \(P=(1,2,\ldots,N)\).
• For \(\displaystyle k=0,1,\ldots,\left\lfloor\frac{N-3}4 \right\rfloor\), swap \(P_{4k+2}\) and \(P_{4k+3}\).

With this procedure, the lower bound for the score is achievable when \(N\equiv 0,1,3\bmod 4\).

From the construction, letting \(P_0=0\), the \(2^k\) places of \(P_{4k},P_{4k+1},P_{4k+2},P_{4k+3}\) are the same for all \(k\geq 2\). By also considering \(k=0,1\) with case analysis on the value of \(N\bmod 4\), one can verify that the lower bound is achieved when \(N\equiv 0,1,3 \bmod 4\).

Consider the case \(N\equiv 2\bmod 4\). Suppose some permutation \(P\) achieves the lower bound for the score derived above. Then, for \(k=1,2,\ldots\), there are an even number of integers between \(1\) and \(N-1\) with a \(1\) in the \(2^k\) place, so we need \(P_N=N\). However, since \(N\) is even and there are an odd number of integers between \(1\) and \(N-1\) with a \(1\) in the \(2^0\) place, this contradicts \(P\) achieving the lower bound for the score. Thus, the lower bound for the score cannot be achieved when \(N\equiv 2\bmod 4\).

However, the lower bound for the score plus \(1\) is achievable with the above construction. Hence, we see that the above procedure achieves the minimum score for all \(N\).

By implementing the above appropriately, this problem can be solved. The time complexity is \(O(N)\) per test case.

Implementation example (Python3)

for _ in range(int(input())):
    n = int(input())
    p = [i + 1 for i in range(n)]
    for i in range(2, n, 4):
        p[i - 1], p[i] = p[i], p[i - 1]
    print(*p)

Proposed by: sounansya