Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBMSEQ - VOI07 Dãy con không giảm dài nhất

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbmseq


Cho dãy số nguyên dương a1, a2, ..., an.

Dãy số: ai, ai+1, ..., aj thỏa mãn ai ≤ ai+1 ≤ ... ≤ aj. Với 1 ≤ i ≤ j ≤ 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ố {uk} xác định bởi u1 = 1, uk = uk-1 + k (k ≥ 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 ≤ 104).

Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương ai (ai ≤ 108) là số hạng thứ i của dãy số đã cho, i = 1, 2, ..., 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).

Example

Input:
8
2
2007
6
6
15
16
3
21
Output:
3


Được gửi lên bởi:special_one
Ngày:2008-09-21
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Vietnam Olympiad of Informatics 2007

hide comments
2021-05-27 18:03:17
Tham khảo: https://vnspoj.github.io/problems/QBMSEQ
2019-09-09 12:33:42
oho, are you approach me?
2019-07-13 12:07:07
DIO was here
2018-09-21 12:13:16
ATTENTION : dãy con phải liên tiếp
2017-10-21 03:24:57
O(N)
u[k]=1+2...+k = (k(k+1))/2
1 đấm
frostpixel aka.How 2 AC

Last edit: 2018-10-29 10:46:48
2017-08-21 16:58:26
Kham khảo thuật toán:
https://vietcodes.github.io/code/54/
2017-05-17 05:21:31
gâu gâu gâu...
2016-12-18 15:43:06
sinh ra dãy U{k}(khoảng 14142 số là vừa đủ) sau đó duyệt O(N) thôi mình ko nghĩ là đề quốc gia có câu dễ v đó
2016-04-07 14:48:06
O(n) cũng 1 đấm AC cần gì TKNP
2016-04-04 11:42:25
1 hit AC vs QHD+TKNP
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.