JOI thích làm vườn và năm nào cũng trồng một loài cây có tên là cây IOI trên mảnh vườn của mình. Mảnh vườn được chia thành \(N\) ô nằm trên một hàng theo hướng đông–tây, đánh số từ \(1\) đến \(N\) theo thứ tự từ phía tây. Có tất cả \(N\) cây IOI, mỗi ô trồng một cây. Đến mùa xuân, cây IOI trồng ở ô \(i\) cao đến độ cao \(h_i\) rồi không cao thêm nữa.

Khi đến thăm vườn vào mùa xuân, JOI phát hiện các cây IOI được bố trí khác với dự định. Cây IOI cần nhiều ánh nắng: nếu ở cả phía có số ô nhỏ hơn và phía có số ô lớn hơn đều có một cây IOI cao hơn nó, cây đó sẽ héo trước khi mùa hè đến. Vì vậy, để không cây IOI nào bị héo, cần thỏa mãn điều kiện sau: với mọi số nguyên \(i\) thỏa mãn \(2 \le i \le N-1\), ít nhất một trong hai điều kiện dưới đây phải đúng.

• Với mọi số nguyên \(j\) thỏa mãn \(1 \le j \le i-1\), ta có \(h_j \le h_i\).
• Với mọi số nguyên \(k\) thỏa mãn \(i+1 \le k \le N\), ta có \(h_k \le h_i\).

Cây IOI rất đắt tiền nên JOI quyết định sắp xếp lại chúng để không cây nào bị héo. Vì cây IOI rất lớn và dễ bị tổn thương, JOI chỉ có thể đổi chỗ hai cây kề nhau. Cụ thể, trong một thao tác, JOI chọn một ô \(i\) bất kỳ (\(1 \le i \le N-1\)) rồi đổi chỗ cây ở ô \(i\) với cây ở ô \(i+1\). Mùa hè càng đến gần, nguy cơ cây bị héo càng cao, nên JOI muốn biết số thao tác ít nhất cần thực hiện để không cây IOI nào bị héo.

Yêu cầu

Cho số ô trong vườn và độ cao của từng cây IOI, hãy viết chương trình tìm số thao tác ít nhất cần thực hiện để sắp xếp lại các cây sao cho không cây nào bị héo.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(N\), là số ô trong vườn của JOI.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N\)) chứa số nguyên \(D_i\), là độ cao của cây IOI ban đầu được trồng ở ô \(i\) khi mùa xuân đến.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là số thao tác ít nhất cần thực hiện.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn:

• \(3 \le N \le 300\,000\).
• \(1 \le D_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).

Phân nhóm

• Nhóm 1 (10 điểm): \(N \le 8\).
• Nhóm 2 (20 điểm): \(N \le 20\).
• Nhóm 3 (15 điểm): \(N \le 5\,000\).
• Nhóm 4 (55 điểm): Không có ràng buộc bổ sung.

Ví dụ

6
2
8
4
5
3
6

3

5
4
4
2
4
4

2

4
1
3
4
2

0