#P1474E. What Is It?
-
ID: 5750
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> What Is It?
No submission language available for this problem.
Description
Lunar rover finally reached planet X. After landing, he met an obstacle, that contains permutation $p$ of length $n$. Scientists found out, that to overcome an obstacle, the robot should make $p$ an identity permutation (make $p_i = i$ for all $i$).
Unfortunately, scientists can't control the robot. Thus the only way to make $p$ an identity permutation is applying the following operation to $p$ multiple times:
- Select two indices $i$ and $j$ ($i \neq j$), such that $p_j = i$ and swap the values of $p_i$ and $p_j$. It takes robot $(j - i)^2$ seconds to do this operation.
Scientists asked you to find out the maximum possible time it will take the robot to finish making $p$ an identity permutation (i. e. worst-case scenario), so they can decide whether they should construct a new lunar rover or just rest and wait. They won't believe you without proof, so you should build an example of $p$ and robot's operations that maximizes the answer.
For a better understanding of the statement, read the sample description.
The first line of input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
Each of next $t$ lines contains the single integer $n$ ($2 \leq n \leq 10^5$) – the length of $p$.
Note, that $p$ is not given to you. You should find the maximum possible time over all permutations of length $n$.
It is guaranteed, that the total sum of $n$ over all test cases doesn't exceed $10^5$.
For each test case in the first line, print how many seconds will the robot spend in the worst case.
In the next line, print the initial value of $p$ that you used to construct an answer.
In the next line, print the number of operations $m \leq n$ that the robot makes in your example.
In the each of next $m$ lines print two integers $i$ and $j$ — indices of positions that the robot will swap on this operation. Note that $p_j = i$ must holds (at the time of operation).
Input
The first line of input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
Each of next $t$ lines contains the single integer $n$ ($2 \leq n \leq 10^5$) – the length of $p$.
Note, that $p$ is not given to you. You should find the maximum possible time over all permutations of length $n$.
It is guaranteed, that the total sum of $n$ over all test cases doesn't exceed $10^5$.
Output
For each test case in the first line, print how many seconds will the robot spend in the worst case.
In the next line, print the initial value of $p$ that you used to construct an answer.
In the next line, print the number of operations $m \leq n$ that the robot makes in your example.
In the each of next $m$ lines print two integers $i$ and $j$ — indices of positions that the robot will swap on this operation. Note that $p_j = i$ must holds (at the time of operation).
Samples
3
2
3
3
1
2 1
1
2 1
5
2 3 1
2
1 3
3 2
5
2 3 1
2
1 3
2 3
Note
For $n = 2$, $p$ can be either $[1, 2]$ or $[2, 1]$. In the first case $p$ is already identity, otherwise robot will make it an identity permutation in $1$ second regardless of choise $i$ and $j$ on the first operation.
For $n = 3$, $p$ can be equals $[2, 3, 1]$.
- If robot will select $i = 3, j = 2$ on the first operation, $p$ will become $[2, 1, 3]$ in one second. Now robot can select only $i = 1, j = 2$ or $i = 2, j = 1$. In both cases, $p$ will become identity in one more second ($2$ seconds in total).
- If robot will select $i = 1, j = 3$ on the first operation, $p$ will become $[1, 3, 2]$ in four seconds. Regardless of choise of $i$ and $j$ on the second operation, $p$ will become identity in five seconds.
We can show, that for permutation of length $3$ robot will always finish all operation in no more than $5$ seconds.