Gửi bài giải


Điểm: 0,72 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
PreVOI 2014
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Giáng Sinh sắp đến, thầy Minh quyết định trang trí khu du lịch của mình. Trước cửa khu du lịch, có một hàng gồm N cây, đánh số từ 1 đến ~N~ theo chiều từ trái sang phải, cây thứ i có độ cao ~h_i~. Thầy Minh quyết định chọn một số cây để treo mỗi cây một đèn lồng đỏ trên ngọn, sao cho khi nhìn từ vịnh Hạ Long vào, các đèn lồng sẽ tạo thành một chữ ~M~.

Chữ ~M~ được định nghĩa như sau: Đó là một dãy các cây, khi xét từ trái sang phải, có thể chia thành 4 phân đoạn, trong đó độ cao các dãy trong đoạn đầu tiên tăng nghiêm ngặt, trong đoạn thứ hai giảm nghiêm ngặt, trong đoạn thứ ba tăng nghiêm ngặt và trong đoạn thứ tư giảm nghiêm ngặt.

Tức là, có một dãy các chỉ số ~a_1~ ~\leq~ ~a_2~ ~\leq~ ... ~\leq~ ~a_i~ ~\leq~ ~b_1~ ~\leq~ ~b_2~ ~\leq~ ... ~\leq~ ~b_j~ ~\leq~ ~c_1~ ~\leq~ ~c_2~ ~\leq~ ... ~\leq~ ~c_k~ ~\leq~ ~d_1~ ~\leq~ ~d_2~ ~\leq~ ... ~\leq~ ~d_l~ sao cho:

  • Dãy ~h_{a1}~, ~h_{a2}~, ..., ~h_{ai}~ là dãy tăng nghiêm ngặt, và ~i \geq 2~.
  • Dãy ~h_{ai}~, ~h_{b1}~, ..., ~h_{bj}~ là dãy giảm nghiêm ngặt, ~j \geq 1~.
  • Dãy ~h_{bj}~, ~h_{c1}~, ..., ~h_{ck}~ là dãy tăng nghiêm ngặt, ~k \geq 1~.
  • Dãy ~h_{ck}~, ~h_{d1}~, ..., ~h_{dl}~ là dãy giảm nghiêm ngặt, ~l \geq 1~.

Độ hoành tráng của chữ ~M~ là số lượng đèn lồng tạo thành chữ ~M~.

Yêu cầu : Hãy tìm độ hoành tráng lớn nhất của một chữ ~M~ mà thầy Minh có thể tạo được.

Input

  • Dòng 1 chứa số nguyên dương ~N \leq 50 000~
  • Dòng 2 chứa ~N~ số nguyên dương không vượt quá ~10^{9}~ .
  • Dữ liệu đảm bảo tồn tại ít nhất một cách treo đèn. Các số trên một dòng của file input được ghi cách nhau bởi dấu cách.

Output

  • Ghi ra độ hoành tráng lớn nhất của một chữ ~M~ có thể có.

Sample Input

15
1 20 15 30 25 20 15 40 30 20 10 5 4 6 8

Sample Output

12

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.