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

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

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 ≤ a i+1 ≤ ... ≤ a j . 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ố {u k } xác định bởi u 1 = 1, u k = u k -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 ≤ 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 ≤ 10 8 ) 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

  • Người up: cun
  • Nguồn bài: Vietnam Olympiad of Informatics 2007