B. Booksort
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Beatriz always enjoyed reading, so she decided to open a bookstore to have books around her all day long. She wants to be sure that the books are properly organized, so she can attract many customers.

On a large shelf of the bookstore there are $$$N$$$ stacks of books in a row, with the stacks numbered from $$$1$$$ to $$$N$$$ left to right. Stack $$$i$$$ contains $$$A_i$$$ books. Beatriz would like the numbers of books to be in non-decreasing order, that is, $$$A_i \le A_{i+1}$$$ for $$${i}={1}, {2}, \ldots, {N-1}$$$, which might require some rearrangement of the books.

However, Beatriz is lazy and she really does not feel like organizing the books by herself. Then she asked her best friend Bernardo for help. They agreed that Beatriz will give Bernardo a sequence of commands. In each command Beatriz will specify two distinct stacks $$$i$$$ and $$$j$$$, and Bernardo will take the $$$s = A_i + A_j$$$ books in those stacks, rearranging them as evenly as possible. This means that after performing the command, the number of books in those stacks will be updated in the following way: $$$$$$ A_i = \left\lfloor \frac{s}{2} \right\rfloor, \qquad A_j = \left\lceil \frac{s}{2} \right\rceil. $$$$$$

Beatriz does not want to spend a lot of time with Bernardo moving around the books for her. She wants a sequence of at most $$$10^{5}$$$ commands that yields the desired non-decreasing order. But, you know, Beatriz does not want to decide the commands by herself. Can you prepare any valid sequence of commands for her?

Input

The first line contains an integer $$$N$$$ ($$$2 \le N \le 5000$$$) indicating the number of book stacks on the shelf. Each stack is identified by a distinct integer from $$$1$$$ to $$$N$$$.

The second line contains $$$N$$$ integers $$${A_1}, {A_2}, \ldots, {A_N}$$$ ($$$1 \le A_i \le 10^{5}$$$), where $$$A_i$$$ is the initial number of books in stack $$$i$$$.

Output

The first line must contain an integer $$$k$$$ ($$$0 \le k \le 10^{5}$$$) indicating the number of commands to perform.

Each of the next $$$k$$$ lines must describe a command with two integers $$$i$$$ and $$$j$$$ ($$$1 \le i,j \le N$$$ and $$$i \neq j$$$), representing that the books in stacks $$$i$$$ and $$$j$$$ are rearranged as described. After performing all the commands in the order in which they appear in your answer, the shelf must be sorted in non-decreasing order.

It can be proven that a valid answer exists under the given constraints. If there are multiple solutions, output any of them; there is no need to minimize $$$k$$$.

Examples
Input
3
1 1 1
Output
0
Input
5
14 7 13 8 15
Output
4
1 2
1 4
2 4
3 4
Note

Explanation for example 1

Since the shelf is initially sorted in non-decreasing order, an empty sequence of commands is a valid output.

Explanation for example 2

Although the shelf is initially sorted, the output is valid because the shelf ends sorted after at most $$$10^{5}$$$ commands. There is no need to minimize the number of commands.

Explanation for example 3

The first command ($$$i = 2$$$, $$$j = 1$$$) changes the shelf from $$$[\underline{14}, \underline{7}, 13, 8, 15]$$$ to $$$[\underline{11}, \underline{10}, 13, 8, 15]$$$.

The second command ($$$i = 1$$$, $$$j = 4$$$) changes the shelf from $$$[\underline{11}, 10, 13, \underline{8}, 15]$$$ to $$$[\underline{9}, 10, 13, \underline{10}, 15]$$$.

The third command ($$$i = 3$$$, $$$j = 4$$$) changes the shelf from $$$[9, 10, \underline{13}, \underline{10}, 15]$$$ to $$$[9, 10, \underline{11}, \underline{12}, 15]$$$, which is sorted in non-decreasing order.