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 \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.

Dữ liệu đầu vào

Gồm hai dòng:

• 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, ..., a_n~ ~(1 \le i \le n;\ a_i \le 10^9)~.

Dữ liệu đầu ra

Gồm 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 dữ liệu

• 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 ... \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 ... \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.

Ví dụ

Ví dụ 1

INPUT

3
2 3 5

OUTPUT

18

Giải thích: Kế hoạch mua thức ăn là:

• Ngày ~1~ mua ~9~ gói với giá là ~2~;
• Ngày ~2, 3~ không mua gói nào.

Số tiền tối thiểu để mua thức ăn là: ~9 \times 2 + 0 \times 3 + 0 \times 5 = 18~.

Ví dụ 2

INPUT

3
5 3 2

OUTPUT

30

Giải thích: Kế hoạch mua thức ăn là:

• Ngày ~1~ mua ~3~ gói với giá là ~5~;
• Ngày ~2~ mua ~3~ gói với giá là ~3~;
• Ngày ~3~ mua ~3~ gói với giá là ~2~.

Số tiền tối thiểu để mua thức ăn là: ~3 \times 5 + 3 \times 3 + 3 \times 2 = 30~.

Ví dụ 3

INPUT

3
5 2 3

OUTPUT

27

Giải thích: Kế hoạch mua thức ăn là:

• Ngày ~1~ mua ~3~ gói với giá là ~5~;
• Ngày ~2~ mua ~6~ gói với giá là ~2~;
• Ngày ~3~ không mua gói nào.

Số tiền tối thiểu để mua thức ăn là: ~3 \times 5 + 6 \times 2 + 0 \times 3 = 27~.