Cho mảng \(A\) gồm \(n\) phần tử và ta có một phép toán như sau:
- Cùng một lúc ta có thể chọn nhiều cặp khác nhau và hoán đổi vị trí chúng cho nhau (Biết rằng các cặp này không được giao nhau).
Hỏi ta cần thực hiện ít nhất bao nhiêu phép toán trên để dãy đã cho không giảm.
Input
-
Dòng thứ nhất chứa số nguyên \(n(1\le n\le 1000)\)
-
Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^9)\)
Output
-
Dòng thứ nhất chứa số \(k\) - số phép toán tối thiểu cần dùng
-
\(k\) dòng tiếp theo, mỗi dòng in ra có dạng như sau: \(p\text{ }i_1\text{ }j_1 \text{ }i_2\text{ }j_2...i_p\text{ }j_p\). Trong đó \(p\) là số cặp ta chọn để hoán đổi vị trí, tiếp theo là \(p\) cặp \((i_u,j_u)(1\le u\le p;i_u\ne j_u)\) thể hiện chỉ số của cặp cần hoán đổi vị trí cho nhau. (Chú ý: Hai cặp chỉ số \(A,B\) gọi là giao nhau nếu tồn tại số \(k\) thỏa mãn \(k\in A\) và \(k\in B\)). Nếu có nhiều đáp án, in ra đáp án bất kì.
Scoring
-
Subtask \(1\) (\(40\%\) số điểm): \(1\le n\le 10\)
-
Subtask \(1\) (\(60\%\) số điểm): Còn lại
Example
Test 1
Input
3
1 3 2
Output
1
1 2 3
Note
Giải thích: Ta chỉ cần chọn một cặp đó là \((2,3)\) thì sẽ được dãy không giảm là \(1,2,3\)
Bình luận
Nếu có nhiều đáp án, in ra đáp án bất kì.
cko em 1 VD dc ko