Трійки Алімжана
У Жарасхана є перестановка, що складається з n різних цілих чисел, де 0 ≤ a[i] < n. Оскільки йому не подобається його друг Алімжан, він хоче змінити свій масив, видаливши мінімальну кількість елементів, щоб у ньому не залишилося жодної трійки Алімжана.
Що таке трійка Алімжана? Це будь-які три послідовні елементи в масиві, які або зростають, або спадають, тобто a[i] < a[i+1] < a[i+2] або a[i] > a[i+1] > a[i+2] для деякого i.
Жарасхан дуже зайнятий зароблянням грошей для Марка у Facebook, тому він попросив вас, учасника KBTU Open, знайти рішення.
Вхідні дані
Перша строка містить одне ціле число n (1 ≤ n ≤ 2 * 10^5). Наступна строка містить n цілих чисел, що описують масив a[i] (0 ≤ a[i] < n), всі елементи якого різні, і який є масивом Жарасхана.
Вихідні дані
Виведіть єдине число - мінімальну кількість елементів, які необхідно видалити з масиву Жарасхана, щоб позбутися всіх трійок Алімжана.
Приклад
У першому прикладі є лише одна трійка Алімжана: [0, 2, 3]. Таким чином, достатньо видалити будь-який з цих 3 елементів.