Trò chơi rải sỏi là một trò chơi khá đơn giản nhưng thú vị, đòi hỏi người chơi cần phải tính toán hợp lí sao cho mỗi lần chơi được kết quả tốt nhất. Trò chơi được mô tả như sau:

Vật dụng cho trò chơi gồm:

- Một bàn cờ có hình vành khăn, mà trên đó người ta đã chia thành N ô nhỏ bằng nhau, các ô được đánh số liên tục từ 1 đến N theo chiều kim đồng hồ.
- Một số ô đã rải sẵn một số viên sỏi.

Ở hình minh họa, ta có bàn cờ được chia thành 6 ô nhỏ bằng nhau tương ứng với N = 6.

Cách chơi:

Người chơi chọn một ô bất kì có chứa sỏi và lấy hết số sỏi này, sau đó chọn cho mình một chiều đi theo chiều kim đồng hồ hoặc ngược lại và suốt một lượt chơi chỉ đi theo chiều này.

Một lượt chơi gồm 2 bước sau:

- Bước 1: Theo chiều đã chọn, qua mỗi ô rải một viên sỏi bắt đầu từ ô liền kề với ô đã chọn, cứ làm như vậy cho đến hết số viên sỏi đã lấy ra. Gọi ô cuối cùng được rải một viên sỏi vào là ô thứ K.
- Bước 2: Người chơi lấy hết các viên sỏi ở ô kề với ô thứ K (theo chiều đã chọn) và dừng lượt chơi.

Yêu cầu: Nếu là người chơi thì với một lượt chơi bạn có thể kiếm được tối đa bao nhiêu viên sỏi?

Dữ liệu vào: 

- Dòng đầu tiên ghi số nguyên dương N (N <= 100).
- Dòng tiếp theo ghi N số nguyên không âm mà số thứ i chính là số viên sỏi đã rải sẵn ở ô thứ i trong bàn cờ (mỗi số cách nhau ít nhất 1 dấu cách). Số sỏi ở mỗi ô trong N ô này đều không vượt quá 10¹² viên.

Kết quả:

Ghi ra một số nguyên M là số viên sỏi nhiều nhất có thể lấy ra được trong một lượt chơi.

Ví dụ

Input

6
0 3 0 1 4 2

Output

3

Giải thích ví dụ: Chọn ô thứ 4 và đi theo chiều ngược chiều kim đồng hồ thì được 3 viên sỏi.

Đề HSG lớp 9 TPĐN 2015-2016