Petya and the Robot

Time limit25sMemory limit1024 MB

Summary

Restore a hidden permutation of 1 to n by swapping two positions and reading the inversion count the Robot reports after each swap.

Level: Medium6 of 10
Topics: Sorting, Binary search, Array
Solved: No attempts yet

Problem

Petya has $n$ notebooks standing on a shelf, containing his complete collection of ideas. The notebooks are numbered with distinct integers from 1 to $n$ . Petya has a usual arrangement of the notebooks on the shelf, which may not be in numerical order, and he dislikes it when anyone rearranges them. Petya bought a special Robot that can memorize an arrangement of notebooks and compute the number of disorders in it. The Robot considers two notebooks to form a disorder if the notebook with the smaller number stands to the right of the notebook with the larger number. For example, in the arrangement $(2, 1, 5, 3, 4)$ there are three disorder pairs, $(2, 1)$ , $(5, 3)$ and $(5, 4)$ , so the number of disorders is 3. After repairing his room, Petya forgot his usual arrangement and wants to restore it. The Robot saved it but can only report the number of disorders in the saved arrangement. Petya can ask the Robot to swap two notebooks in the saved arrangement. After such a request, the Robot saves the new arrangement and reports its number of disorders. Petya can repeat requests until he decides he has enough information to restore the usual arrangement. Write a program that communicates with the Robot and restores the usual arrangement.

Constraints

$1 \leqslant n \leqslant 100\,000$

Examples1

Example 1
Input
```
3 2
1
0
```
Expected output
```
swap 1 3
swap 3 2
answer 2 3 1
```