Tin tức tình báo thu được cho thấy quân địch sắp mở cuộc tấn công quy mô. Biên quan cử người phóng ngựa về kinh thành báo cáo tình hình và xin tiếp viện. Giữa biên quan và kinh thành có bố trí ~N - 2~ dịch trạm cách đều nhau, ở đó người đưa tin có thể đổi sang con ngựa mới. Ngựa của trạm ~i~ có thể chạy tới trạm kế tiếp sau thời gian ~T_i~ giờ. Mỗi con ngựa đều đủ khỏe để có thể đi một mạch tới tận kinh thành.

Hãy xác định khoảng thời gian ngắn nhất tin tức được đưa về tới kinh thành.

Input

• Dòng đầu là số nguyên ~N~ ~(2 < N ≤ 1000)~.
• ~N~ dòng tiếp theo là ~N~ số nguyên ~T_i~ là thời gian con ngựa ở trạm ~i~ cần để chạy đến dịch trạm kế tiếp ~(0 < T_i ≤ 10000)~.

Output

• Gồm 1 dòng duy nhất là giá trị cần tìm.

Sample Input

5
2
4
3
1
5

Sample Output

7