Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài, gắn chặt xuống mặt bàn rồi đánh số thứ tự các máy từ 1 đến N theo chiều từ trái sang phải. Các học sinh tinh nghịch quyết định tìm cách nối các máy trên bàn bởi các đoạn dây sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành, họ đã đo khoảng cách giữa hai máy liền kề.

Yêu cầu

Hãy giúp các học sinh tìm cách nối mạng thỏa mãn điều kiện sao cho tổng độ dài cáp phải sử dụng là nhỏ nhất.

Input

• Dòng đầu tiên chứa số lượng máy N (1 ≤ N ≤ 25000).
• Dòng thứ i trong số N-1 dòng tiếp theo chứa khoảng cách từ máy i đến máy i+1 (i = 1, 2, …, N-1). Giả thiết rằng khoảng cách từ máy 1 đến máy N không vượt quá 10^6.

Output

Ghi ra độ dài cáp nối cần sử dụng nhỏ nhất.

Ví dụ

6
2
3
2
2
3

7