Roger has a secret array ~a_1, a_2, \dots, a_N~. Every number from ~1~ to ~N~ 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 ~i, j~ 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 ~a~ is the number of pairs of indices ~(i, j)~ for which ~i<j~ and ~a_i>a_j~.

Constraints

For all subtasks:

At most ~4\,000~ swaps are allowed.

Subtask 1 [10%]

~1 \le N \le 80~

Subtask 2 [10%]

~1 \le N \le 200~

Subtask 3 [30%]

~1 \le N \le 1\,000~

Subtask 4 [50%]

~1 \le N \le 2\,000~

Input Specification

The first and only line of input is a single integer, ~N~.

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 ~1~ and ~N~ 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 ~4\,000~ 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