Bajtazar has decided to clean his room!

However, it is not going very well. One of the problems he encountered while cleaning is arranging $n$ books on a shelf. There are $n$ positions on the shelf, numbered from $1$ to $n$, and each position contains exactly one book. Let us number the books from $1$ to $n$ such that, in the final state, book $1$ should be at position $1$, book $2$ at position $2$, and so on. Bajtazar can quickly determine the number of inversions in the current arrangement. An inversion is defined as a pair of distinct positions $i$ and $j$ such that $i < j$, where the books at these positions are $p_i$ and $p_j$ respectively, and $p_i > p_j$.

Your task is to help Bajtazar arrange the books on his shelf. You can perform at most $m$ operations. One operation consists of choosing any two positions (possibly the same), swapping the books currently located there, and then receiving information from Bajtazar about the number of inversions in the current arrangement. After all your swaps, the books on Bajtazar's shelf should be sorted, meaning they are arranged in the order $1, 2, \dots, n$.

Communication

This is an interactive problem. You must write a program that performs operations on Bajtazar's books so that they are sorted at the end. In this task, communication with the grader can be done either using a library or via standard input and output. You choose which option you prefer. Do not use both methods simultaneously.

A sample implementation of both types of communication can be found in the files provided to the contestant.

Your program must not open any files. The program may use standard diagnostic output (stderr), but remember that this consumes valuable time. Any excessive data printed to standard output may be treated as an incorrect answer.

Option 1: Communication via library

C++ At the beginning of the program, you must include: #include "porlib.h" The library provides the following functions: int DajN() – Returns the number of books $n$. int Zamiana(int a, int b) – Swaps the books at positions $a$ and $b$ ($1 \le a, b \le n$); the function returns the number of inversions after the swap. When this function returns $0$, the books are sorted, and your program should terminate without making further library function calls.

Python At the beginning of the program, you must include: from porlib import DajN, Zamiana The library provides the following functions: DajN() – Returns the number of books $n$. Zamiana(a : int, b : int) – Swaps the books at positions $a$ and $b$ ($1 \le a, b \le n$); the function returns the number of inversions after the swap. When this function returns $0$, the books are sorted, and your program should terminate without making further library function calls.

General Information Library functions can be called in any order, and the one returning the number of books $n$ can be called multiple times. Using any function with incorrect arguments will result in a "Wrong Answer" verdict. Similarly, reading from standard input and writing to standard output may result in a "Wrong Answer" verdict.

Option 2: Communication via standard input/output

The first line of standard input will contain a single integer $n$, representing the number of books. Then, the grader waits for two integers $a$ and $b$, representing the positions to swap; you must print them to standard output, separated by a single space and followed by a newline character. Then, you must read one integer from standard input, representing the number of inversions after the swap.

When you read $0$, the books are sorted, and your program should terminate without further interaction with standard input and output.

C++, stream I/O You must include the appropriate header (#include <iostream>). At the end of each line when printing, you must use std::endl. Example start of communication:

std::cin >> n;
std::cout << a << ' ' << b << std::endl;
std::cin >> number_of_inversions;

C++, stdio You must include the appropriate header (#include <cstdio>). After printing each line, you must call fflush(stdout). Example start of communication:

scanf("%d", &n);
printf("%d %d\n", a, b);
fflush(stdout);
scanf("%lld", &number_of_inversions);

Python After printing each line, you must use flush=True. Example start of communication:

n = int(input())
print(f"{a} {b}", flush=True)
number_of_inversions = int(input())

Examples

Example 1

Suppose the initial arrangement of books is $1, 3, 2, 4, 6, 5$, and the limit on the number of swaps is $m = 1000$. The program execution for such data might look as follows:

Scoring

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

You may assume that in each test, the initial order of books on the shelf is determined first, and only then are the operations on the books handled.

For the contestant

In the dlazaw directory, there are example (incorrect) solutions in C++ and Python that illustrate both communication models. Libraries for communication and an example checker are also available.

• por.cpp – example solution demonstrating communication using std::cin and std::cout.
• por.py – example solution demonstrating communication using input() and print(...).
• por2.cpp – example solution demonstrating communication using porlib.h.
• por2.py – example solution demonstrating communication using porlib.py.

To compile the example C++ solutions and the checker, you can use the make command, which creates the files por.e and por2.e.

The program can be run using the run.sh script. For example, all the above programs can be run with the commands:

• ./run.sh "./por.e"
• ./run.sh "python3 por.py"
• ./run.sh "./por2.e"
• ./run.sh "python3 por2.py"

The executed program reads data from the input.in file in the following format: in the first line: two integers $n$ and $m$, in the second line: a permutation of numbers $1, \dots, n$ describing the initial arrangement of books.

Numbers should be separated by single spaces.

The example checker is different from the one used in SIO. In particular, the example program may not check the correctness of the input or function call arguments. When you submit your solution to SIO, it will be checked on the example tests using the proper checker.

Note. Trial runs are not available for this task.