Đề bài

Sắp xếp nổi bọt (Bubble sort) là một trong những thuật toán dùng để sắp xếp một dãy số. Giả sử chúng ta muốn sắp xếp một dãy số $A$ có độ dài $N$ theo thứ tự tăng dần. Sắp xếp nổi bọt sẽ hoán đổi vị trí của $2$ số đứng cạnh nhau nếu quan hệ thứ tự giữa chúng bị ngược. Một lượt duyệt bao gồm việc quét dãy số từ đầu đến cuối, tức là với $i = 1, 2, \dots, N - 1$ theo đúng thứ tự này, nếu $A_i > A_{i+1}$ thì hoán đổi $2$ số đó. Người ta đã biết rằng việc lặp lại lượt duyệt này $N - 1$ lần sẽ sắp xếp được dãy số theo thứ tự tăng dần.

Số lần hoán đổi bằng sắp xếp nổi bọt trên dãy $A$ là số lần các số nguyên được hoán đổi khi áp dụng thuật toán trên cho dãy $A$. (Mặc dù 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ể có những khác biệt nhỏ về thứ tự vòng lặp, phạm vi và điều kiện dừng, người ta biết rằng số lần hoán đổi số nguyên khi áp dụng cho cùng một dãy số sẽ không thay đổi bởi những khác biệt đó.)

Ví dụ, chương trình dưới đây là một hàm được viết bằng ngôn ngữ C để sắp xếp một 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]) {
        /* The following 3 lines correspond to 1 swap of integers */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

Yêu cầu

Cho một dãy số $A$ có độ dài $N$. Giả sử ta tạo ra một dãy số $A'$ bằng cách hoán đổi $2$ số nguyên ở vị trí bất kỳ trong dãy $A$ đúng $1$ lần. Hãy viết chương trình tìm giá trị nhỏ nhất của số lần hoán đổi bằng sắp xếp nổi bọt trên dãy $A'$. (Lưu ý rằng $2$ số nguyên được hoán đổi lúc đầu không nhất thiết phải đứng cạnh nhau.)

Giới hạn

• $1 \le N \le 100000$: độ dài của dãy $A$.
• $1 \le A_i \le 1000000000$: độ lớn của các số trong dãy $A$.

Dữ liệu vào

Đọc dữ liệu sau từ Đầu vào chuẩn:

• Dòng thứ $1$ ghi số nguyên $N$. $N$ biểu thị độ dài của dãy $A$.
• Dòng thứ $i$ ($1 \le i \le N$) trong $N$ dòng tiếp theo ghi số nguyên $A_i$. Số này biểu thị số nguyên thứ $i$ của dãy $A$.

Dữ liệu ra

In ra Đầu ra chuẩn trên $1$ dòng một số nguyên biểu thị số lần hoán đổi nhỏ nhất bằng sắp xếp nổi bọt trên dãy $A'$.

Tiêu chí chấm điểm

• Trong dữ liệu chấm, $10\%$ số điểm thỏa mãn $N \le 1000$, và $A_i \ne A_j$ với mọi $i, j$ ($1 \le i < j \le N$).
• Trong dữ liệu chấm, $30\%$ số điểm thỏa mãn $N \le 5000$, và $A_i \ne A_j$ với mọi $i, j$ ($1 \le i < j \le N$).
• Trong dữ liệu chấm, $80\%$ số điểm thỏa mãn $A_i \ne A_j$ với mọi $i, j$ ($1 \le i < j \le N$).

Ví dụ

Ví dụ đầu vào 1

5
10
3
6
8
1

Ví dụ đầu ra 1

0

Nếu ta hoán đổi số $10$ đầu tiên và số $1$ cuối cùng của dãy $A$, dãy $A'$ sẽ trở thành một dãy đã được sắp xếp, và số lần hoán đổi trong sắp xếp nổi bọt là $0$.

Ví dụ đầu vào 2

5
3
1
7
9
5

Ví dụ đầu ra 2

2

Bằng cách hoán đổi số $7$ ở vị trí thứ $3$ và số $5$ ở cuối dãy $A$, dãy $A'$ trở thành $3, 1, 5, 9, 7$. Số lần hoán đổi bằng sắp xếp nổi bọt trên $A'$ là $2$.

Ví dụ đầu vào 3

3
1
2
3

Ví dụ đầu ra 3

1

Ngay cả khi dãy $A$ đã được sắp xếp ngay từ đầu, ta vẫn bắt buộc phải thực hiện một phép hoán đổi khi tạo dãy $A'$.