CF1375E Inversion SwapSort

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.

N/A

N/A

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.