eolymp

Тройки Алимжана

У Жарасхана есть перестановка, состоящая из n различных целых чисел, где 0ai < n. Но поскольку ему не нравится его друг Алимжан, то он хочет изменить свой массив, удалив такое наименьшее количество элементов, чтобы в нем не осталась ни одна тройка Алимжана.

Вы спросите, что такое тройка Алимжана? Что ж, Алимжан описывает ее как любые три последовательных элемента в массиве, которые либо возрастают, либо убывают, то есть ai < ai+1 < ai+2 или ai > ai+1 > ai+2 для некоторого i.

Жарасхан очень занят зарабатыванием денег для Марка в Facebook, поэтому он попросил Вас - участника этого самого KBTU Open, найти ответ.

Входные данные

Первая строка содержит одно целое число n (1n2 * 105). Следующая строка содержит n целых чисел, описывающих массив ai (0ai < n), все элементы которого различны, который и является массивом Жарасхана.

Выходные данные

Выведите единственное число - минимальное количество элементов, которое необходимо удалить из массива Жарасхана, чтобы освободить его от троек Алимжана.

Пример

В первом примере присутствует только одна тройка Алимжана: [0, 2, 3]. Таким образом, достаточно удалить любой из этих 3 элементов.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
0 2 3 1
Çıxış verilənləri #1
1
Giriş verilənləri #2
5
0 2 1 4 3
Çıxış verilənləri #2
0
Giriş verilənləri #3
6
3 0 5 2 1 4
Çıxış verilənləri #3
1
Mənbə 2021 KBTU Open, Весна Казахстан, Алма-Ата, 30 мая, Задача G