Limits 3s, 512 MB

There are NN posts in a line numbered from 11 to NN from left to right. Each post ii has a distance did_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, 1d1<d2<d3<<dN1\leq d_1 < d_2 < d_3 < … < d_N.

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

To keep the discipline, you will give the following commands one at a time. Choose two distinct posts, ii and jj where (1i,jN)(1\leq i,j\leq N), and swap the troops. All soldiers currently stationed at post ii will go to post jj and all soldiers currently stationed at post jj will go to post ii. When moving from post ii to jj, one soldier needs to walk didj|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 (1T100)T\ (1\leq T\leq 100) which denotes the number of test cases.

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

The next line will contain NN space separated integers d1, d2, d3,, dNd_1,\ d_2,\ d_3, …,\ d_N where did_i denotes the distance of post ii from base. 1di107, di<di+1 for all 1i<N1\leq d_i\leq 10^7,\ d_i < d_{i+1}\text{ for all }1\leq i< N.

The next line will contain NN more space separated integers P1, P2, P3,, PNP_1,\ P_2,\ P_3, …,\ P_N. Troop currently stationed at post ii should be stationed at post PiP_i after all the commands are given. 1PiN and all Pi are distinct1\leq P_i\leq N\text{ and all }P_i\text{ are distinct}, so PP is a permutation of length NN.

It is guaranteed that the sum of NN over all test cases does not exceed 10610^6.


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


1 10 20
2 3 1
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.