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.|

PVOI14_4 - Chữ M

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/pvoi14_4


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 < a_2 < ... < a_i < b_1 < b_2 < ... < b_j < c_1 < c_2 < ... < c_k < d_1 < d_2 < ... < d_l sao cho:

  • Dãy h_a1, h_a2, ..., h_ai là dãy tăng nghiêm ngặt, và i ≥ 2.
  • Dãy h_ai, h_b1, ..., h_bj là dãy giảm nghiêm ngặt, j  1.
  • Dãy h_bj, h_c1, ..., h_ck là dãy tăng nghiêm ngặt, k ≥ 1.
  • Dãy h_ck, h_d1, ..., h_dl là dãy giảm nghiêm ngặt, l ≥ 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 ≤ 50,000
  • Dòng 2 chứa N số nguyên dương không vượt quá 109
  • 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ó.

Example

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

Output:
12

Được gửi lên bởi:VOJ Team
Ngày:2014-12-15
Thời gian chạy:1s
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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:PreVOI 2014

hide comments
2014-12-19 08:41:07 [ND]๖ۣۜMiniString
bai nay lam sao vay?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.