SPSEQ - Sequences

Giới hạn
  • Thời gian: 0.104s
  • 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

 

W. là 1 dãy các số nguyên dương. Nó có các đặc điểm sau:

  • Độ dài của dãy là 1 số lẻ: L = 2*N + 1
  • N + 1 số nguyên đầu tiên của dãy tạo thành 1 dãy tăng
  • N + 1 số nguyên cuối của dãy tạo thành 1 dãy giảm
  • Không có 2 số nguyên nào cạnh nhau trong dãy có giá trị bằng nhau

Ví dụ: 1, 2, 3, 4, 5, 4, 3, 2, 1 là 1 dãy W. độ dài 9 . Tuy nhiên, dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 không là 1 dãy W.

Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy W. có độ dài dài nhất.

Input

Dòng 1: số nguyên dương N (N <= 100000), độ dài dãy số.

Dòng 2: N số nguyên dương a i (a i <= 10 9 ).

Output

1 số nguyên dương duy nhất là độ dài dãy W. dài nhất.

Example

Input:
10
1 2 3 4 5 4 3 2 1 10

Output:
9

Input:
19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

Output:
9

  • Người up: hnue
  • Nguồn bài: UVA