Vì tình trạng chơi game trong giờ Tin học diễn ra thường xuyên, nên 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à sắp xếp chúng thành một dãy trên một cái bàn dài. Ngoài ra, máy tính được gắn chặt xuống mặt bàn rồi đánh thứ tự từ \(1 \to n\) theo chiều từ trái sang phải. Dù vậy, các học sinh không chịu thua, họ đã 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 nối sao chô mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Tuy vậy, để tiết kiệm, các học sinh muốn tổng độ dài dây cáp nối là ít nhất. Bạn hãy giúp các học sinh tìm cách nối mạng thỏa mãn yêu cầu đặt ra.

INPUT:

• Dòng đầu tiên chứa số lượng máy n \((1 \le n \le 25000)\).
• Dòng thứ i trong số n-1 dòng tiếp theo là khoảng cách từ máy i đến máy i+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:

• Là độ dài thỏa mãn yêu cầu.

Ví dụ: