Sắp xếp nổi bọt là một thuật toán sắp xếp dãy. Giả sử ta muốn sắp xếp dãy số \(A\) có độ dài \(N\) theo thứ tự tăng dần. Thuật toán xét các cặp số kề nhau theo thứ tự từ đầu dãy; nếu một cặp đang sai thứ tự thì đổi chỗ hai số đó. Cụ thể, trong một lượt duyệt, lần lượt với \(i=1,2,\ldots,N-1\), nếu \(A_i>A_{i+1}\) thì đổi chỗ hai số này. Ta biết rằng lặp lại lượt duyệt đó \(N-1\) lần sẽ sắp xếp được dãy theo thứ tự tăng dần.

Số lần đổi chỗ của sắp xếp nổi bọt đối với dãy \(A\) là số lần hai số nguyên được đổi chỗ khi áp dụng thuật toán trên cho \(A\). Các thuật toán và cách cài đặt được gọi là sắp xếp nổi bọt có thể khác nhau đôi chút về thứ tự, phạm vi vòng lặp hoặc điều kiện kết thúc. Tuy nhiên, khi áp dụng cho cùng một dãy, số lần đổi chỗ không thay đổi bởi những khác biệt này.

Chẳng hạn, hàm C dưới đây sắp xếp mảng số nguyên a có độ dài n bằng sắp xếp nổi bọt:

void bubble_sort(int *a, int n) {
  int i, j;
  for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < n - 1; ++j) {
      if (a[j] > a[j + 1]) {
        /* Ba dòng sau tương ứng với một lần đổi chỗ hai số nguyên. */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

Yêu cầu

Cho dãy số \(A\) có độ dài \(N\). Ta tạo dãy \(A'\) bằng cách chọn hai số nguyên ở các vị trí tùy ý trong \(A\) và đổi chỗ chúng đúng một lần. Hãy viết chương trình tìm số lần đổi chỗ nhỏ nhất của sắp xếp nổi bọt đối với dãy \(A'\). Lưu ý rằng hai số được đổi chỗ ban đầu không nhất thiết phải kề nhau.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), là độ dài của dãy \(A\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1\le i\le N\)) chứa số nguyên \(A_i\), là số thứ \(i\) của dãy \(A\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là số lần đổi chỗ nhỏ nhất của sắp xếp nổi bọt đối với dãy \(A'\).

Ràng buộc

• \(1\le N\le100000\).
• \(1\le A_i\le1000000000\) (\(1\le i\le N\)).

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le1000\) và \(A_i\ne A_j\) với mọi \(1\le i<j\le N\).
• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le5000\) và \(A_i\ne A_j\) với mọi \(1\le i<j\le N\).
• \(80\%\) số điểm dành cho các dữ liệu thỏa mãn \(A_i\ne A_j\) với mọi \(1\le i<j\le N\).

5
10
3
6
8
1

0

Đổi chỗ số \(10\) ở đầu dãy \(A\) và số \(1\) ở cuối dãy. Khi đó \(A'\) đã được sắp xếp, nên số lần đổi chỗ của sắp xếp nổi bọt bằng \(0\).

5
3
1
7
9
5

2

Đổi chỗ số \(7\) ở vị trí thứ \(3\) của \(A\) và số \(5\) ở cuối dãy, ta được \(A'=(3,1,5,9,7)\). Số lần đổi chỗ của sắp xếp nổi bọt đối với \(A'\) là \(2\).

3
1
2
3

1

Ngay cả khi dãy \(A\) đã được sắp xếp từ đầu, vẫn phải thực hiện một lần đổi chỗ để tạo ra dãy \(A'\).