Bạn được cho số nguyên dương ~ n ~ và dãy số nguyên ~ a_1, a_2,…,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ố ~ [1,3,2] ~ bạn có thể lấy số 3 đặt vào phía sau số 2, dãy số được chuyển thành ~ [1,2,3] ~.

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 ≤ n ≤ 5 × 10^5 ) ~
• ~ n ~ dòng sau lần lượt các số nguyên ~ a_1, a_2, …,a_n ~ ~ ( 1 ≤ a_i ≤ 10^9 ) ~

Kết quả

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

Ví dụ:

Input 1

3
1 3 2 

Output 1

1