Найбільша пилкоподібна підпослідовність#2211
Послідовність чисел називається пилкоподібною, якщо кожен її елемент (окрім першого й останнього) або більший за обох своїх сусідів, або менший за обох своїх сусідів. Наприклад, послідовність 1, 2, 1, 3, 2 є пилкоподібною, тоді як 1, 2, 3, 1, 2 — ні, оскільки 1 < \textbf{2} < \textbf{3}. Будь-яка послідовність, що складається з одного елемента, вважається пилкоподібною. Послідовність із двох елементів є пилкоподібною, якщо її два елементи не рівні.
Перший рядок містить одне ціле число (1 \leq N \leq 100\,000) — кількість елементів послідовності. Другий рядок містить натуральних чисел, кожне з яких не перевищує — елементи послідовності.
Виведіть одне ціле число: мінімальну кількість елементів, які потрібно видалити.
Приклад 1