Giải bài trực tuyến

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á 10⁹. 
• 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