CSES - KILO 2018 1/5 - Interesting Inversions
  • Time limit: 2.00 s
  • Memory limit: 512 MB

This is an interactive problem.

Uolevi and Maija are playing a game together. First Maija chooses an integer n and an array v_1, v_2, \dots, v_n that has each integer between 1 \dots n exactly once. Uolevi knows the number n but doesn't know the array.

Uolevi can then make queries by choosing two integers i and j such that i\le j. Then Maija reverses the subarray v_i, v_{i+1}, \dots, v_{j-1}, v_j and tells Uolevi the number of inversions in v. An inversion is a pair of integers such that i < j and v_i > v_j.

Uolevi wins the game if the array is sorted after an operation, i.e., the number of inversions is 0. Uolevi may make at most 4n queries.

Can you win the game for Uolevi?

Interaction

The first input line has a single integer n: the size of the array v.

To make a query, output two integers i and j, 1 \leq i \leq j \leq n, in a new line. You need to flush the output stream after this.

After every query, the next input line has a single integer: the number of inversions in the array after the operation. If the number is 0, you win. It doesn't matter what your program does after you win.

If you do 4n queries but do not win, your program will get the "Wrong Answer" verdict.

Constraints

  • 1\leq n\leq 1000
  • You may make at most 4n queries.

Example

in: 2
out: 1 2
in: 1
out: 1 2
in: 0

Explanation: Here the array is initially [1,2]. After the first query, the array becomes [2,1] and there is one inversion. After the second query, the array becomes [1,2]. Now there are no inversions and victory is achieved.