АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
Textbooks FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

1432. Sequence

Time Limit: 1 seconds
Memory Limit:262144KB
Points:100
View Problem Statistics Submit Problem added 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

 

 


View Problem Statistics Submit Problem discussion Author/source:
Problems from Contests / Vologda Students Contests / XVIII Interuni Olympiad 2015 /
1431. E - Fraction 1432. 1433. G - Olympiad 1434. H - Speed Check 1435. I - DNA Analysis
time generating 0.079 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.