BigZero có một bể cá với đàn cá nhiều màu sắc. Hằng ngày sau những giờ học bài, cậu thường ngồi ngắm đàn cá và cho chúng ăn. Thức ăn của cá được đựng trong các gói đóng sẵn. Mỗi ngày đàn cá ăn hết đúng 3 gói, giá bán thức ăn thường xuyên biến động. Cửa hàng cho biết trước giá bán trong n ngày lần lượt là \(a_{1},\ a_{2},...,\ a_{n}\), mỗi ngày được mua nhiều gói với giá bán của ngày đó, thức ăn thừa có thể được dùng cho các ngày tiếp theo. BigZero đang lên kế hoạch để mua thức ăn cho đàn cá trong n ngày sao cho tiết kiệm nhất.

Yêu cầu: Cho số nguyên dương n và các số nguyên dương \(a_{1}\),\(\ a_{2},...,\ a_{n},\) trong đó \(a_{i}\) là giá bán một gói thức ăn trong ngày thứ \(i\ (1 \leq i \leq n \leq 10^{6};\ a_{i} \leq 10^{9})\). Hãy xác định số tiền tối thiểu để mua thức ăn cho đàn cá trong \(n\) ngày.

Dữ liệu vào:

• Dòng thứ nhất chứa một số nguyên dương \(n\ (1 \leq n \leq 10^{6})\).

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},\ a_{2},...,\ a_{n}\ (1 \leq i \leq n;\ a_{i} \leq 10^{9})\).

Kết quả: Ghi một số nguyên duy nhất là số tiền tối thiểu để mua thức ăn cho đàn cá trong n ngày.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: \(a_{1} \leq a_{2} \leq \ ... \leq a_{n}\).

• Có 30% số test khác ứng với 30% số điểm của bài thỏa mãn:.

• 40% số test còn lại ứng với 40% số điểm của bài không có ràng buộc gì thêm.

Ví dụ: