Mô tả và yêu cầu

Tèo có một hàng cây gồm 𝑁 cây cảnh được đánh s ố thứ tự từ 1 đến N từ đầu hàng
đến cuối hàng. Lúc mới trồng, tất cả các cây cảnh có chiều cao bằng nhau. Một thời
gian sau, do cây phát triển không đồng đều nên trong hàng có cây cao cây th ấp. Để
làm tăng vẻ đẹp của hàng cây, Tèo quyết định loại bỏ một số cây để hàng cây thoả
mãn một trong hai điều kiện: hoặc là chiều cao của các cây nhìn từ đầu hà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 nhìn
từ đầu hàng phải giảm dần (cây đứng sau thấp hơn cây đứng trước).
Yêu cầu: Hãy tính xem phải loại bỏ những cây cảnh trong hàng như thế nào để số
cây bị bỏ là ít nhất.
Dữ liệu: vào từ thiết bị nhập chuẩn
 Dòng 1: số nguyên dương 𝑁(𝑁 ≤ 105) là số cây cảnh có trong dãy.
 Dòng 2: ghi 𝑁 số nguyên 𝑎1, 𝑎2, … ,𝑎𝑁(1 ≤ 𝑎𝑖 ≤ 109) là chiều cao của các
cây.
Kết quả: Ghi ra thiết bị xuất chuẩn chứa số nguyên duy nhất là số cây cảnh bị phá
bỏ thỏa mãn yêu cầu của đề bài.

Ví dụ

INPUT                            OUTPUT
               5                                 1
               1 4 2 3 6

Giới hạn:
      40% số test có 𝑁     ≤  25;
      30% số test tiếp theo có 𝑁      ≤  2000;
      30% số test cuối cùng có 𝑁       ≤  105.