Một luống hoa thẳng tắp có \(n\) cây hoa được đánh số thứ tự từ 1 đến \(n\) kể từ đầu luống. Lúc mới trồng, tất cả các cây hoa đều có chiều cao bằng nhau. Sau một thời gian do cây phát triển không đồng đều nên trong luống có cây cao, cây thấp nhìn không được đẹp lắm. Để làm cho luống hoa đẹp, người ta quyết định cắt bỏ một số cây để luống hoa sau khi cắt bỏ thỏa một trong hai điều kiện: hoặc là chiều cao của các cây hoa nhìn từ đầu luống phải tăng dần (cây đứng sau cao hơn cây đứng trước); hoặc là chiều cao của các cây hoa nhìn từ đầu luống phải giảm dần (cây đứng sau thấp hơn cây đứng trước).

Yêu cầu: Tính số lượng cây cắt bỏ ít nhất để luống hoa trở nên đẹp.

Dữ liệu:

• Dòng đầu ghi số nguyên dương \(n (1<n≤2000)\) là số cây hoa trong luống.

• Dòng thứ hai ghi \(n\) số nguyên dương \(a_1,a_2,…,a_n\) với \(a_i\) là chiều cao của cây thứ \(i (a_i ≤ 10^3,1≤i≤n)\).

Các số trên cùng một dòng được ghi cách nhau một khoảng trắng.

Kết quả:

• Một dòng duy nhất ghi một số nguyên là số cây hoa ít nhất sẽ cắt bỏ.

Sample Input

5
1 4 2 3 6

Sample Output

1