M. Task For Benq
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One week before the contest, CULC organizers learned that a certain highly rated coder will participate. In shock, they quickly opened TaskGPT, and, with trembling fingers, typed:

ikaurovcan u make task for benq asap? make no mistakes
TaskGPTFantastic question! The following task would be a great fit.
You are given a list $$$a$$$ of $$$n$$$ non-negative integers, where $$$n \leq 1000$$$. You can perform the following operation on this list zero or more times.

Choose two distinct positions $$$1 \le x,y \le n$$$ and assign: $$$$$$a_x := a_x \oplus a_y$$$$$$ Above, $$$\oplus$$$ is the bitwise XOR of the two numbers.

You need to perform these operations so that the resulting list is sorted in non-decreasing order — i.e., $$$a_i \le a_{i+1}$$$ for each position $$$i$$$ from $$$1$$$ to $$$n-1$$$. The final set of numbers does not have to match the initial one.

You must sort the list using at most $$$2500$$$ operations. Would you like to know the solution?

Input

The first line contains the number $$$n$$$ ($$$1 \leq n \leq 1000$$$), the size of the list.

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2^{20}-1$$$), the list to be sorted.

Output

On the first line, print the number of operations $$$m$$$ ($$$0 \leq m \leq 2500$$$).

On the following $$$m$$$ lines, print $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \neq y$$$) — the positions selected on each operation.

The list must be sorted in non-decreasing order after the $$$m$$$ operations.

It can be shown that it is always possible to sort the list using at most $$$2500$$$ operations.

Examples
Input
5
0 1 1 1 2
Output
0
Input
5
4 3 2 1 0
Output
5
5 1
1 5
2 3
2 4
4 3
Note

In the first test case, the list is already sorted, so nothing needs to be done.

In the second test case, the list evolves as follows: $$$[4, 3, 2, 1, 0] \to [4, 3, 2, 1, 4] \to [0, 3, 2, 1, 4] \to [0, 1, 2, 1, 4] \to [0, 0, 2, 1, 4] \to [0, 0, 2, 3, 4]$$$.