eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Наибольшая пилообразная подпоследовательность

Наибольшая пилообразная подпоследовательность

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 - нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.

Дана последовательность. Требуется определить, какое наименьшее количество ее членов нужно вычеркнуть, чтобы оставшаяся последовательность оказалась пилообразной.

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

В первой строке входного файла записано одно число N (1N100000) - количество членов последовательности. Во второй строке записано N натуральных чисел, не превосходящих 10000 - члены последовательности.

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

В выходной файл выведите одно число - минимальное количество членов, которые необходимо вычеркнуть.

Пример

Входные данные #1
5
1 2 3 1 2
Выходные данные #1
1