Nhà Bờm có ~n~ máy tính xếp thẳng hàng (cố định) được đánh số từ ~1~ đến ~n~. Bờm muốn nối các máy tính lại với nhau sao cho mỗi máy tính được nối với ít nhất một máy tính khác. Biết khoảng cách giữa hai máy liên tiếp thứ ~i~ và thứ ~i + 1~ là ~d_i~ ~(i = 1, 2, …, n – 1)~. Em hãy giúp Bờm tính xem tổng độ dài dây cáp ít nhất Bờm cần phải sử dụng nhé.

Input

• Dòng đầu chứa số nguyên dương ~n~;
• Dòng thứ hai chứa ~n - 1~ số nguyên dương ~d_1, d_2, …, d_{n - 1}~.

Giới hạn:

• ~1 ≤ N ≤ 25000; 1 ≤ d_i < 10^4~.

Output

• Một số nguyên duy nhất là tổng độ dài dây cáp Bờm cần dùng.

Sample

Input #1

6
2 2 3 2 2

Output #1

7

Hint

Cách nối máy của Bờm:

Problem source: Chuyên Sơn La Online Judge