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

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

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

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

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

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

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

Пример

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