Dãy số x = (x₁, x₂, . . ., x_k) được gọi là dãy răng cưa, nếu k > 2 và x₁ khác x₂  và nếu lấy ra 3 số bất kỳ liên tiếp nhau thì số ở giữa là số có giá trị nhỏ nhất  hoặc giá trị lớn nhất duy nhất của 3 số đó. Ví dụ: dãy (1, 2, 1, 3, 2) là dãy răng cưa, còn dãy (1, 2, 3, 1, 2) không phải là dãy răng cưa vì dãy 3 số đầu 1, 2, 3 có số ở giữa không nhỏ nhất cũng không lớn nhất.

            Yêu cầu: Cho số n và dãy số nguyên a₁, a₂, . . ., a_n (3 ≤ n ≤ 100000, 1 ≤ a_i ≤ 1000). Hãy xác định số lượng tối thiểu các phần tử cần xoá trong dãy để các phần tử còn lại tạo thành dãy số răng cưa.

Dữ liệu vào: Cho từ tệp văn bản DAYSO.INP gồm:

• Dòng đầu ghi số phần tử n.
• Các dòng tiếp theo lần lượt ghi giá trị các phần tử của dãy số a₁, a₂, ...,a_n. Các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách.

Kết quả: Ghi vào tệp văn bản DAYSO.OUT gồm một số nguyên xác định số phần tử cần xóa

Ví dụ: