Nuôi cá cảnh

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, \dots, 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, \dots, a_n$, trong đó $a_i$ là giá bán một gói thức ăn trong ngày thứ $i$ ($1 \le i \le n \le 10^6$; $a_i \le 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.

Vào từ tệp văn bản FISH.INP:

• Dòng thứ nhất chứa một số nguyên dương $n$ ($1 \le n \le 10^6$).
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($1 \le i \le n$; $a_i \le 10^9$).

Ghi ra tệp văn bản FISH.OUT 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.

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: $a_1 \le a_2 \le \dots \le a_n$.
• Có 30% số test khác ứng với 30% số điểm của bài thỏa mãn: $a_1 \ge a_2 \ge \dots \ge a_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.