Задача Zigzag

Послідовність чисел називається зигзагом, якщо в ній немає жодної монотонно незростаючої і жодної монотонно спадної підпослідовності елементів, що розташовані послідовно,  завдовжки 3. Дано послідовність. Яку мінімальну кількість елементів необхідно вставити в неї, щоб вийшов зигзаг?
Технічні умови:
Програма зчитує з клавіатури кількість елементів послідовності N (3<=N<=10000) і N чисел-елементів послідовності (кожен не більший 1000 за абсолютною  величиною). Всі числа вводяться одним рядком через пропуск. Програма виводить на екран одне число – шукану величину.

Приклад: 
Введення: 6 1 4 7 9 7 4
Выведення: 3


Задача Zigzag

Последовательность чисел называется зигзагом, если в ней нет ни одной монотонно невозрастающей и ни одной монотонно неубывающей подпоследовательности подряд идущих элементов длиной 3. Дана последовательность. Какое минимальное количество элементов необходимо вставить в нее, чтобы получился зигзаг?
Технические условия: Программа читает с клавиатуры количество элементов последовательности N (3<=N<=10000) и N чисел - элементы последовательности (не большие 1000 по абсолютной величине каждый). Все числа вводятся одной строкой через пробел. Программа выводит на экран единственное число – искомую величину.
Пример: 
Ввод: 6 1 4 7 9 7 4
Вывод: 3

© LIKT 1998-2018