Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Inversion SwapSort

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMadeline has an array $$$a$$$ of $$$n$$$ integers. A pair $$$(u, v)$$$ of integers forms an inversion in $$$a$$$ if:

- $$$1 \le u < v \le n$$$.
- $$$a_u > a_v$$$.

Madeline recently found a magical paper, which allows her to write two indices $$$u$$$ and $$$v$$$ and swap the values $$$a_u$$$ and $$$a_v$$$. Being bored, she decided to write a list of pairs $$$(u_i, v_i)$$$ with the following conditions:

- all the pairs in the list are distinct and form an inversion in $$$a$$$.
- all the pairs that form an inversion in $$$a$$$ are in the list.
- Starting from the given array, if you swap the values at indices $$$u_1$$$ and $$$v_1$$$, then the values at indices $$$u_2$$$ and $$$v_2$$$ and so on, then after all pairs are processed, the array $$$a$$$ will be sorted in non-decreasing order.

Construct such a list or determine that no such list exists. If there are multiple possible answers, you may find any of them.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the array.

Next line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — elements of the array.

Output

Print -1 if no such list exists. Otherwise in the first line you should print a single integer $$$m$$$ ($$$0 \le m \le \dfrac{n(n-1)}{2}$$$) — number of pairs in the list.

The $$$i$$$-th of the following $$$m$$$ lines should contain two integers $$$u_i, v_i$$$ ($$$1 \le u_i < v_i\le n$$$).

If there are multiple possible answers, you may find any of them.

Examples

Input

3 3 1 2

Output

2 1 3 1 2

Input

4 1 8 1 6

Output

2 2 4 2 3

Input

5 1 1 1 2 2

Output

0

Note

In the first sample test case the array will change in this order $$$[3,1,2] \rightarrow [2,1,3] \rightarrow [1,2,3]$$$.

In the second sample test case it will be $$$[1,8,1,6] \rightarrow [1,6,1,8] \rightarrow [1,1,6,8]$$$.

In the third sample test case the array is already sorted.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/15/2021 22:17:48 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|