QUEUE - Xếp hàng
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.5 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: dahaodl

Trong buổi khai mạc hội thi Duyên hải 2017 tổ chức tại trường chuyên Lương Văn Tụy, tất cả các khối môn đều xếp hàng ngay ngắn, người đứng sau không thấp hơn người đứng trước, chỉ có duy nhất khối 10 môn Tin học đã xếp thành một hàng nhưng chưa xếp đúng thứ tự cao thấp. Thầy Đinh Văn Khâm là hiệu trưởng trường chuyên Lương Văn Tụy (cũng là cựu học sinh của trường đạt cả giải quốc gia môn Toán học và môn Tin học) nhanh chóng áp dụng thuật toán sắp xếp để đưa ra một dãy các thao tác đổi chỗ, mỗi thao tác thực hiện việc đổi chỗ hai bạn, bạn đang đứng ở vị trí thứ i với bạn đứng ở vị trí thứ j. Sau dãy thao tác đổi chỗ, khối 10 môn Tin học đã xếp thành một hàng mà người đứng sau không thấp hơn người đứng trước. Nhân dịp này, thầy Khâm muốn kiểm tra các bạn tham gia thi Duyên Hải năm 2017 môn Tin học khối lớp 10 nội dung về sắp xếp. Bài toán như sau: Cho một dãy gồm n số nguyên a[1], a[2], ... , a[n] hãy đưa ra dãy các thao tác đổi chỗ để nhận được dãy không giảm.

Dữ liệu:
- Dòng đầu chứa số nguyên n;
- Dòng thứ hai chứa n số nguyên a[1], a[2], ... , a[n] (−10^9 ≤ a[1], a[2], ... , a[n] ≤ 10^9), các số cách nhau bởi dấu cách.

Kết quả: Gồm một số dòng, mỗi dòng chứa hai số i, j (1 ≤ i, j ≤ n; i ≠ j) mô tả một phép đổi chỗ phần tử ở vị trí thứ i với phần tử ở vị trí thứ j.

Ràng buộc: n <= 10^5

Ví dụ

QUEUE.INP QUEUE.OUT
4
3 4 1 2
1 3
2 4

 

Back to Top