Тройки Алимжана
У Жарасхана есть перестановка, состоящая из 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 элементов.