Задача №1587. Пилообразная последовательность
Числовая последовательность называется пилообразной, если каждый ее элемент (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 — нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.
Дана последовательность. Требуется определить, какое наименьшее количество ее элементов нужно вычеркнуть, чтобы оставшаяся последовательность оказалась пилообразной.
На вход программе сначала подается значение \(n \le 100 000\) — количество членов последовательности. Во второй строке записаны \(n\) натуральных чисел, не превосходящих 10 000 — члены последовательности.
Выведите одно число — минимальное количество элементов, которые необходимо вычеркнуть.
5 1 2 3 1 2
1
5 1 2 1 3 2
0
5 1 2 3 4 5
3
5 1 1 2 1 1
2