ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1346. Интервалы монотонности

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Всем известно, что область определения любой непрерывной функции можно разбить на интервалы, на которых функция монотонно возрастает или убывает. Назовём сложностью разбиения количество интервалов в нём. Тогда сложность непрерывной функции — это минимально возможная сложность разбиения области определения на интервалы монотонности.
Понятие сложности может быть введено не только для непрерывных функций. Например, это можно сделать для функций, определённых на сетке.

Исходные данные

Ввод содержит описание функции F, определённой на сетке. Первая строка содержит 2 числа A и B — начало и конец целочисленной сетки с шагом 1 (0 ≤ A < B ≤ 100 000). Во второй строке перечислена таблица значений функции F. Таблица состоит из целых чисел F(A), F(A+1), …, F(B), разделённых пробелами и/или переводами строк. Все значения функции F лежат в диапазоне от –100 000 до 100 000.

Результат

Выведите единственное число — сложность функции F.

Пример

исходные данныерезультат
1 10
1 2 3 4 2 1 -1 3 6 7
3
Автор задачи: Александр Клепинин
Источник задачи: USU Championship 2004