Số nghịch thế

Cho một mảng gồm $n$ số nguyên $a_1,a_2,a_3,\dots ,a_n$ là một hoán vị của các số từ $1$ đến $n$. Số nghịch thế của một mảng là số cặp $(i,j)$ thỏa mãn $1\le i<j\le n$ và $a_i>a_j$.

Bạn được thực hiện một phép biến đổi trên mảng như sau:

• Chọn một số nguyên $x$ có giá trị từ $1$ đến $n$.
• Mọi phần tử nhỏ hơn $x$ được chuyển sang bên trái của $x$, và mọi phần tử lớn hơn $x$ được chuyển sang bên phải của $x$.
• Thứ tự tương đối giữa các phần tử nhỏ hơn $x$, cũng như giữa các phần tử lớn hơn $x$, phải giữ nguyên sau phép biến đổi.

Ví dụ, với mảng $[6,2,3,5,1,4]$ và $x=4$, sau phép biến đổi mảng trở thành $[2,3,1,4,6,5]$ và có ba nghịch thế. Còn nếu chọn $x=5$ thì mảng trở thành $[2,3,1,4,5,6]$ và chỉ có hai nghịch thế.

Yêu cầu: Tìm số nghịch thế nhỏ nhất của mảng sau khi thực hiện phép biến đổi (phép biến đổi được thực hiện đúng một lần).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$: số phần tử của mảng.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra số nghịch thế nhỏ nhất.

Ràng buộc

• $1\le n\le {10}^6$.
• $a_1,a_2,\dots ,a_n$ là một hoán vị của $1,2,\dots ,n$.

Ví dụ