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 hi. 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ố \(a1<a2<…<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_{a_1},h_{a_2},…,h_{a_i}\) là dãy tăng nghiêm ngặt \(i \geq 2\).
• Dãy \(h_{a_i},h_{b_1},…,h_{b_j}\) là dãy giảm nghiêm ngặt \(j \geq 1\).
• Dãy \(h_{b_j},h_{c_1},…,h_{c_k}\) là dãy tăng nghiêm ngặt \(k \geq 1\).
• Dãy \(h_{c_k},h_{d_1},…,h_{d_l}\) 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 50000\)
• Dòng 2 chứa n số nguyên dương không vượt quá \(10^9\)

Output

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

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 50;\)
• Subtask \(2\) (\(50\%\) số điểm): \(n \leq 1000;\)
• Subtask \(3\) (\(15\%\) số điểm): \(h_i \leq 1000;\)
• Subtask \(4\) (\(15\%\) số điểm): \(n \leq 50000,hi \leq 10^9\)

Example

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

12