(mistep.*)

Bạn được cho số nguyên dương \(n\) và dãy số nguyên \(a_{1},a_{2},\ldots,a_{n}\). Trong mỗi bước bạn cần lấy một phần tử ở vị trí bất kỳ và đặt nó vào trước hoặc sau một phần tử khác. Ví dụ cho dãy số \(\lbrack 1,3,2\rbrack\) bạn có thể lấy số 3 đặt vào phía sau số 2, dãy số được chuyển thành \(\lbrack 1,2,3\rbrack\).

Yêu cầu: Hãy thực hiện ít bước nhất sao cho dãy số trở thành dãy tăng hoặc giảm.

Dữ liệu vào:

- Dòng đầu tiên chứa số nguyên dương \(n\ (1 \leq n \leq 5 \times 10^{5})\)

- \(n\) dòng sau lần lượt các số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{9})\)

Dữ liệu ra:

• Một số nguyên duy nhất cho biết kết quả của bài toán.

Ví dụ: