Cho mảng hoán vị \(A\) độ dài \(n\). Mỗi thao tác, bạn có thể chọn 2 phần tử cạnh nhau \(A_i\) và \(A_{i + 1}\) và đổi chỗ chúng. Tìm số lượng thao tác ít nhất để sắp xếp lại hoán vị theo thứ tự tăng dần.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).

Output

• In ra số lượng thao tác ít nhất.

Điều kiện

• \(1 \le n \le 10^6\).

Ví dụ

Input:

4
2 4 1 3

Output:

3