VOI 07 Bài 1 - Dãy con không giảm dài nhất

View as PDF

Submit solution


Points: 0.09 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Vietnam Olympiad of Informatics 2007
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy số nguyên dương ~a_{1}~, ~a_{2}~, ..., ~a_{n}~.

Dãy số: ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~ thỏa mãn ~a_{i} \leq a_{i+1} \leq \dots \leq a_{j}~ . Với ~1 \leq i \leq j \leq n~ được gọi là dãy con không giảm của dãy số đã cho và khi đó số ~j-i+1~ được gọi là độ dài của dãy con này.

Yêu cầu: Trong số các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy số {~u_{k}~} xác định bởi ~u_{1} = 1~, ~u_k = u_{k-1} + k~ ~(k \geq 2)~, hãy tìm dãy con có độ dài lớn nhất.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~ ~(n \leq 10^{4})~.

Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương ~a_{i}~ ~(a_{i} \leq 10^{8})~ là số hạng thứ ~i~ của dãy số đã cho, ~i = 1, 2, \dots, n~.

Output

Gồm 1 dòng duy nhất ghi số nguyên ~d~ là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì ~d = 0~).

Sample Input

8
2
2007
6
6
15
16
3
21

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.