Trung thu sắp đến, Bờm 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}\). Bờm 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ừ ngoài 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} < \ldots < a_{i} < b_{1} < b_{2} < \ldots < b_{j} < c_{1} < c_{2} < \ldots < c_{k} < d_{1} < d_{2} < \ldots < d_{l}\) sao cho:

• Dãy \(h_{a1},\ h_{a2},\ldots,h_{ai}\) là dãy tăng nghiêm ngặt \(i \geq 2.\)

• Dãy \(h_{ai},\ h_{b1},\ \ldots,h_{bj}\) là dãy giảm nghiêm ngặt \(j \geq 1.\)

• Dãy \(h_{bj},\ h_{c1},\ldots,h_{ck}\) là dãy tăng nghiêm ngặt \(k \geq 1.\)

• Dãy \(h_{ck},\ h_{d1},\ldots,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à Bờm có thể tạo được.

Dữ liệu vào:

• 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 input file được ghi cách nhau bởi dấu cách.

Kết quả: In ra độ hoành tráng lớn nhất của một chữ M có thể có.

Ví dụ:

Giải thích: Các cây tạo thành hình chữ M có độ cao là: \(1\ 20\ 30\ 25\ 20\ 15\ 40\ 30\ 20\ 10\ 5\ 4\). Độ hoành tráng là 12.

Ràng buộc:

• 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 50\ 000;h_{i} \leq 10^{9}\)