Giải bài trực tuyến

Cho dãy A là một hoán vị gồm N số. Một nghịch thế là một cặp số u, v sao cho u < v và A_u > A_v. Bạn được thực hiện thao tác đổi chỗ hai số bất kì trong dãy A không quá một lần. Hãy tính số nghịch thế nhỏ nhất có thể đạt được trong dãy A.

Input

• Dòng 1 chứa số nguyên dương N.
• Dòng 2 chứa N số nguyên dương A₁, A₂, ..., A_N.

Output

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

Giới hạn

• N ≤ 1000
• A_i ≤ N

Trong 70% số test, N ≤ 100.

Example

Input

5

4 5 2 3 1

Output

3