Cho một mảng số nguyên $A$ có kích thước $N$, thao tác xáo trộn (shuffle) được định nghĩa như sau:

• Ban đầu, bạn tạo một mảng số nguyên $B$ rỗng.
• Sau đó, khi $A$ chưa rỗng, bạn loại bỏ phần tử ngoài cùng bên trái hoặc ngoài cùng bên phải của $A$, và thêm giá trị đó vào bên phải của $B$.
• Nếu $A$ rỗng, thay thế $A$ bằng $B$ và dừng lại.

Nếu thao tác xáo trộn được thực hiện như hình trên, giá trị của mảng $A$ sẽ thay đổi như sau:

$(34, 19, 5, 36, 4, 25, 12, 9) \to (9, 34, 19, 12, 25, 4, 5, 36)$.

Gọi $A_i$ là phần tử thứ $i$ của mảng $A$. Khi điều kiện "nếu $1 \le i < j \le N$, thì $A_i \le A_j$" được thỏa mãn, ta nói mảng $A$ tăng đơn điệu.

Hãy viết chương trình, cho trước một mảng số nguyên $A$ có kích thước $N$, tính số lượng thao tác xáo trộn tối thiểu cần thiết để làm cho mảng $A$ tăng đơn điệu.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$, số lượng phần tử trong mảng $A$ ($1 \le N \le 3 \cdot 10^5$). Dòng thứ hai chứa $N$ số nguyên $A_1, \dots, A_N$: các giá trị ban đầu của các phần tử trong mảng $A$ ($1 \le A_i \le 10^9$).

Dữ liệu ra

In ra số lượng thao tác xáo trộn tối thiểu cần thiết để làm cho mảng $A$ tăng đơn điệu.

Ví dụ

Dữ liệu vào 1

3
2 2 5

Dữ liệu ra 1

0

Dữ liệu vào 2

6
1 5 8 10 3 2

Dữ liệu ra 2

1