Олимпиады по программированию

olympiads.ru

Олимпиады прошлых лет
2020/21
2019/20
2018/19
2017/18
2016/17
2015/16
2014/15
2013/14
2012/13
2011/12
2010/11
2009/10
2008/09
2007/08
2006/07

I Всероссийская заочная олимпиада школьников по информатике (2006/07)
Документы
Информация об олимпиаде
Обращение к организаторам региональных олимпиад
Регионы, участвующие в олимпиаде
Задачи и результаты
Задачи
Тесты и решения
Персональная страничка участника
Предварительные результаты
Результаты проверки решений на похожесть
Окончательные результаты
Дипломы
Статистика
Дополнительная информация
FAQ по работе с тестирующей системой
Несколько советов участникам олимпиад
Связаться с оргкомитетом

I Всероссийская заочная олимпиада школьников по информатике, 2006/07 учебный год

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

Имя входного файла: g.in
Имя выходного файла: g.out
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта

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

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

Формат входных данных

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

Формат выходных данных

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

Примеры

g.in g.out
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