Cho trước một mảng gồm \(n\) số nguyên phân biệt. Tại mỗi lượt, bạn có thể đảo vị trí của hai phần tử kề nhau.

Bạn muốn biến đổi mảng này thành dạng kim tự tháp. Nghĩa là mảng kết quả đầu tiên phải tăng dần, và sau đó giảm dần. Cho phép mảng cuối cùng chỉ tăng hoặc chỉ giảm.

Số lượng lượt đi tối thiểu là bao nhiêu?

Input

• Dòng đầu vào đầu tiên chứa \(n\): kích thước của mảng.
• Dòng tiếp theo chứa \(n\) số nguyên phân biệt \(x_1, x_2, \dots, x_n\): nội dung của mảng.

Output

• In một số nguyên: số lượng nước đi tối thiểu.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)

Example

Sample input:

4
2 1 5 3

1

Note

Bạn có thể đổi chỗ hai phần tử đầu tiên, tạo nên mảng hình "kim" \([1,2,5,3]\)