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