shiba quyết định sẽ đi chợ tìm mì tôm về ăn. Chợ có tất cả \(N\) gói mì tôm, gói mì tôm thứ \(i\) có trọng lượng là \(W_i\). Do là người phàm ăn, shiba đã ăn hết tất cả các gói mì tôm trong chợ. Sau khi về đến nhà, shiba mới chợt nhớ ra là cậu ấy chưa cầm gói nào về nhà cả vì vậy cậu ấy quyết định sẽ trở lại chợ để mua mì cầm về nhà.

Tuy nhiên, do shiba đã ăn quá no nên cậu ấy sẽ không thể tự bê mì về được mà cần thuê xe kéo hàng. Cậu ấy cũng không nhớ rõ là gói mì tôm thứ \(i\) có trọng lượng là bao nhiêu, mà cậu ấy nhớ như sau: Giả sử có một dãy \(A\) gồm \(N - 1\) số nguyên, thì giá trị của \(A_i\) lớn hơn hoặc bằng trọng lượng lớn nhất của một trong hai gói mì \(W_i\) và \(W_{i+1}\).

Căng da bụng, trùng da mắt, shiba quyết định nhờ _minhduc ghi lại trọng lượng của từng gói mì tôm sao cho tổng trọng lượng của \(N\) gói mì tôm là lớn nhất có thể và đúng với điều kiện shiba đã nêu ra. Bạn hãy in ra tổng trọng lượng lớn nhất có thể của \(N\) gói mì tôm đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((2 \le N \le 100)\).
• Dòng tiếp theo chứa \(N-1\) số nguyên \(A_1,A_2,...,A_{N-1}\) \((0 \le A_i \le 10^5)\).

Output

• In ra đáp án sau khi thực hiện yêu cầu bài toán.

Example

3
1 3

5