Roger has a secret array . Every number from to appears exactly once in this array. Roger needs help with sorting his array, but he doesn't want to show it to you. Instead, he will let you choose indices to swap and after each swap, he will only tell you the number of inversions of the array. Help Roger sort his array!
Clarification: The number of inversions of an array is the number of pairs of indices for which and .
Constraints
For all subtasks:
At most swaps are allowed.
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [30%]
Subtask 4 [50%]
Input Specification
The first and only line of input is a single integer, .
Interaction
This is an interactive problem. After reading the initial line of input, your program can make updates.
Each update must be a single line containing two space-separated integers, indicating which indices to swap. These integers must be between and and do not have to be distinct.
After printing, a new line with a single integer will appear as input. This integer is the number of inversions in the secret array after swapping.
Once you believe the array is sorted, print a single line containing 0
. If the array is not sorted at this point, you will receive a WA
verdict. Otherwise, you will receive AC
.
You may make at most swaps (note that the final 0
is not considered a swap).
Sample Interaction
>>>
denotes your output. You should not print this in your actual program.
4
>>>1 1
4
>>>4 3
5
>>>1 2
6
>>>1 4
1
>>>2 3
0
>>>0
Explanation for Sample
The original array is 3 4 1 2
.
The array, after the swaps, is
3 4 1 2
3 4 2 1
4 3 2 1
1 3 2 4
1 2 3 4
Comments