Задача 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