Bạn có điểm số của một số người chơi trong một cuộc thi và cần lập bảng xếp hạng theo thứ tự điểm giảm dần.

Cấu trúc dữ liệu lưu danh sách chỉ hỗ trợ một thao tác: chuyển người chơi ở vị trí \(i\) đến vị trí \(j\) mà không thay đổi thứ tự tương đối của những người chơi khác. Nếu \(i > j\), vị trí của những người đang ở từ \(j\) đến \(i-1\) tăng thêm \(1\); nếu \(i < j\), vị trí của những người đang ở từ \(i+1\) đến \(j\) giảm đi \(1\).

Việc tìm người chơi ở vị trí \(i\) tốn \(i\) bước và tìm vị trí \(j\) tốn \(j\) bước, nên chi phí của thao tác là \(i+j\). Các vị trí được đánh số từ \(1\).

Hãy tìm một dãy thao tác đưa danh sách về thứ tự điểm giảm dần sao cho tổng chi phí nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\), số người chơi. Mỗi trong \(n\) dòng tiếp theo chứa một số nguyên không âm \(s_i\), là điểm của người chơi ở vị trí hiện tại thứ \(i\). Mọi điểm số đôi một khác nhau.

Dữ liệu ra

Dòng đầu in số thao tác \(k\). Mỗi trong \(k\) dòng tiếp theo chứa hai số nguyên \(i\), \(j\), mô tả thao tác chuyển người chơi hiện ở vị trí \(i\) đến vị trí \(j\). Các thao tác được thực hiện theo đúng thứ tự đã in.

Danh sách cuối cùng phải có điểm giảm dần và tổng chi phí của các thao tác phải nhỏ nhất có thể.

Ràng buộc

Phân nhóm

• \(30\%\) số phép thử có \(n \le 10\).

Ví dụ

5
20
30
5
15
10

2
2 1
3 5