Cho một dãy hoán vị độ dài ~n~. Lihwy sẽ thực hiện thao tác sau đúng một lần: Chọn ra một dãy con (không cần liên tiếp) ~a_{i_1}, a_{i_2}, \cdots, a_{i_{k - 1}}, a_{i_k}~ (~1 \le i_1 < i_2 < \cdots < i_k \le n~) và đảo ngược dãy con đó thành ~a_{i_k}, a_{i_{k - 1}}, \cdots, a_{i_2}, a_{i_1}~.

Một dãy hoán vị ~a~ độ dài ~n~ là dãy có các số nguyên từ ~1~ đến ~n~ xuất hiện đúng một lần trong dãy. Một nghịch thế là một cặp chỉ số (~i, j~) mà ~i < j~ và ~a_i > a_j~.

Hãy giúp Lihwy tính số nghịch thế nhỏ nhất có thể của dãy sau khi thực hiện thao tác nhé !

Input

Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 5000~) - độ dài của dãy hoán vị.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~). Các số nguyên này đôi một phân biệt.

Output

In ra số nghịch thế nhỏ nhất có thể của dãy sau khi thực hiện thao tác.

Scoring

Sample Input 1

5
5 4 2 3 1

Sample Output 1

1

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Notes

Trong ví dụ thứ nhất, ta có thể chọn dãy con ~[5, 4, 2, 1]~ và đảo ngược nó thành ~[1, 2, 4 , 5]~. Khi đó ta có dãy mới ~[1, 2, 4, 3, 5]~ có số nghịch thế là ~1~.

Trong ví dụ thứ hai, ta có thể chọn dãy con ~[2]~. Khi đó dãy không đổi và có số nghịch thế là ~0~.