# #P1375E. Inversion SwapSort

ID: 873 Type: RemoteJudge 2000ms 256MiB 尝试: 3 已通过: 3 难度: 9 上传者: 标签>constructive algorithmsgreedysortings*2500

# Inversion SwapSort

## Description

Madeline 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.

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.

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.

## 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.

## Samples

3
3 1 2

2
1 3
1 2

4
1 8 1 6

2
2 4
2 3

5
1 1 1 2 2

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.