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 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 3 phần, trong đó độ cao các câ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_0 < a_1 < \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_{a_1}, h_{a_2}, \ldots, h_{a_i}~ là dãy tăng nghiêm ngặt với ~i \geq 2~.

• Dãy ~h_{a_i}, h_{b_1}, \ldots, h_{b_j}~ là dãy giảm nghiêm ngặt với ~j \geq 1~.

• Dãy ~h_{b_j}, h_{c_1}, \ldots, h_{c_k}~ là dãy tăng nghiêm ngặt với ~k \geq 1~.

• Dãy ~h_{c_k}, h_{d_1}, \ldots, h_{d_l}~ là dãy giảm nghiêm ngặt với ~l \geq 1~.

Độ hoành tráng của chữ M là số lượng đèn lồng tạo thành chữ M. 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.

Input

Dòng đầu tiên là một số nguyên dương ~N~ (~1 \le N \le 50000~) — số cây.

Dòng thứ hai là ~N~ số nguyên dương ~h_1, h_2, \ldots, h_N~ (~1 \le a_i \le 10^9~) — độ cao của các cây.

Output

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.

Scoring

Sample Input 1

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

Sample Output 1

12

Notes

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