Задана последовательность целых чисел 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
|
