АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1432. Последовательность

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Задана последовательность целых чисел A. Необходимо выбрать из нее подпоследовательность B. Назовем пару соседних элементов последовательности B неправильной, если Bi > Bi+1. Ваша задача — найти длину такой максимальной последовательности B, чтобы количество неправильных пар в ней не превышало одной.

Например, для последовательности (4, 8, 5, 1, 7, 2, 7) искомой подпоследо-вательностью может быть (4, 5, 1, 7, 7).

 

Входные данные. В первой строке входных данных содержится целое число N (1 ≤ N ≤ 105) – количество чисел в последовательности А.

В следующей строке содержится N целых чисел, разделенных пробелом (0 ≤ Ai ≤ 109, 1 ≤ i ≤ N) – элементы последовательности.

 

Выходные данные. Выведите одно искомое число длину максимальной подпоследовательности.

 

Примеры

Входные данные

Выходные данные

7

4 8 5 1 7 2 7

5

4

4 3 2 1

2

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XVIII межвузовская олимпиада 2015 /
1431. E - Дробь 1432. 1433. G - Олимпиада 1434. H - Контроль скорости 1435. I - Анализ ДНК
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.