Sắp xếp chèn

Xét thuật toán sắp xếp chèn (insertion sort) dùng để sắp xếp một mảng $a$ có $n$ phần tử theo thứ tự không giảm:

for (int i = 1; i < n; i = i + 1) {
    int j = i;
    while (j > 0 && a[j] < a[j - 1]) {
        swap(a[j], a[j - 1]);
        j = j - 1;
    }
}

Mảng $a$ là một hoán vị của các số từ $0$ đến $n-1$.

Trước khi chạy thuật toán, ta được phép chọn đúng hai vị trí trong mảng và hoán đổi giá trị tại hai vị trí đó. Hãy chọn cặp vị trí sao cho số lần hàm swap được gọi khi chạy thuật toán trên mảng sau khi hoán đổi là nhỏ nhất có thể.

Dữ liệu bảo đảm luôn tồn tại một cách hoán đổi hai phần tử làm giảm số lần gọi swap.

Cần in ra số lần gọi swap nhỏ nhất đạt được, và số cặp vị trí $(i,j)$ mà việc hoán đổi hai phần tử tại chúng đạt được số lần gọi nhỏ nhất đó.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $n$, độ dài hoán vị.
• Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau từ $0$ đến $n-1$, mô tả hoán vị.

Dữ liệu ra

In ra hai số nguyên: số lần gọi hàm swap nhỏ nhất, và số cặp $(i,j)$ đạt được số lần gọi nhỏ nhất đó.

Ràng buộc

• $2\le n\le 5000$

Ví dụ