Inversion SwapSort

题意翻译

给定一个长度为 $n$ 的序列 $a$，求 $a$ 中的所有逆序对 $(i_1, j_1), (i_2, j_2), \cdots, (i_m, j_m)$ 的一个排列 $p$， 使得依次交换 $(a_{i_{p_1}}, a_{j_{p_1}}), (a_{i_{p_2}}, a_{j_{p_2}}), \cdots, (a_{i_{p_m}}, a_{j_{p_m}})$ 后序列单调不降。 $1 \le n \le 10^3$，$1 \le a_i \le 10^9$。

题目描述

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.

输入输出样例

输入样例 #1

3
3 1 2

输出样例 #1

2
1 3
1 2

输入样例 #2

4
1 8 1 6

输出样例 #2

2
2 4
2 3

输入样例 #3

5
1 1 1 2 2

输出样例 #3

0

说明

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.