Limits
3s, 512 MB

There are $N$ posts in a line numbered from $1$ to $N$ from left to right. Each post $i$ has a distance $d_i$ which describes how far it is from the base of operation. The more left you go, the closer you get to the base. More formally, $1\leq d_1 < d_2 < d_3 < … < d_N$.

Each post has a different number of soldiers. Post $i$ has a troop of $i$ soldiers. Now it is time for the drill and you need to shuffle the positions of the troops. You want the troop $i$ to go the position $P_i$ for all $1\leq i\leq N$.

To keep the discipline, you will give the following commands one at a time. Choose two distinct posts, $i$ and $j$ where $(1\leq i,j\leq N)$, and swap the troops. All soldiers currently stationed at post $i$ will go to post $j$ and all soldiers currently stationed at post $j$ will go to post $i$. When moving from post $i$ to $j$, one soldier needs to walk $|d_i - d_j|$ unit of distance.

You can give **as many** commands as you want until each troop is at its desired position but you want to do it such that the total distance crossed by all soldiers is as **minimum** as possible. You also want to **minimize** the total number of commands **after** minimizing total distance crossed.

The first line of the input will contain an integer, $T\ (1\leq T\leq 100)$ which denotes the number of test cases.

Each of the test cases starts with one integer $N\ (1\leq N\leq 10^6)$ describing the number of posts.

The next line will contain $N$ space separated integers $d_1,\ d_2,\ d_3, …,\ d_N$ where $d_i$ denotes the distance of post $i$ from base. $1\leq d_i\leq 10^7,\ d_i < d_{i+1}\text{ for all }1\leq i< N$.

The next line will contain $N$ more space separated integers $P_1,\ P_2,\ P_3, …,\ P_N$. Troop currently stationed at post $i$ should be stationed at post $P_i$ after all the commands are given. $1\leq P_i\leq N\text{ and all }P_i\text{ are distinct}$, so $P$ is a **permutation** of length $N$.

It is guaranteed that the sum of $N$ over all test cases does not exceed $10^6$.

For each test case output two integers $C$ and $Q$ in the first line, where $C$ is the minimum distance crossed by all soldiers and $Q$ is the minimum number of commands needed to do that. Then output $Q$ more lines, each of them will contain two integers $i,j\ (i\neq j,\ 1\leq i,j\leq N)$ which denotes a command. **NOTE: Troop currently stationed at post** $i$ **must be stationed at post** $P_i$ **after all** $Q$ **commands are applied in chronological order. First you need to minimize** $C$**, then minimize** $Q$**. If there are multiple sets of commands of size** $Q$ **so that the total distance crossed remains** $C$**, print any of them.**

Input | Output |
---|---|

2 3 1 10 20 2 3 1 4 1 2 3 4 3 4 1 2 | 86 2 3 2 2 1 20 2 3 1 4 2 |

Login to submit.

0%
Solution Ratio

Toph uses cookies. By continuing you agree to our Cookie Policy.