Phong đang tổ chức một gian hàng "Thiện xạ Thần tài". Có \(n\) thùng đựng xu được xếp liên tiếp thành một hàng ngang, đánh số từ \(1\) tới \(n\) từ trái sang phải. Người chơi biết được trước lượng xu trong mỗi thùng. Mỗi người được phát một khẩu súng bắn nịt (với số lượng dây chun, nịt, ... là vô hạn) khi bắn trúng mục tiêu có khả năng làm đổ 1 thùng. Phong bố trí các thùng, sao cho thùng thứ \(i\) có \(a_i\) xu. Luật chơi như sau: Với các thùng đã được bố trí trước, người chơi sẽ lần lượt bắn đổ các thùng và nhận xu, lượng xu nhận được sẽ là \(\min(a,b)\) với \(a,b\) là lượng xu của hai thùng chưa đổ, gần nhất về bên trái và bên phải của thùng mới bị bắn đổ. Nếu bắn vào thùng ngoài cùng bên trái hoặc bên phải, người chơi không nhận được xu.

Nobita là một tay thiện xạ với biệt tài bách phát bách trúng, nhưng cậu ấy khá dở trong các bài toán tối ưu. Hỏi rằng lượng xu lớn nhất mà Nobita nhận được là bao nhiêu?

Yêu cầu: Cho trước số \(n\) và dãy \(a\). Theo luật chơi ở trên, hãy tính số xu lớn nhất có thể nhận được và đưa ra màn hình.

Input

• Dòng đầu tiên chứa số nguyên dương \(n (1\le n\le 5\cdot 10^5)\)
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n (1 \le a_i \le 10^6)\)

Output

Gồm một dòng duy nhất in ra số xu tối đa nhận được.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 1000\)
• Subtask \(3\) (\(30\%\) số điểm): giới hạn gốc

Example

5
3 1 5 2 6

11

5
1 2 3 4 5

6

5
1 100 101 100 1

102