Farmer John quên vá lỗ hàng rào nên $N$ bò $(1 \le N \le 1,000)$ thoát và phá phách! Mỗi con ngoài rào gây hại một đô la mỗi phút. FJ phải tới từng con buộc dây cương để làm dịu và dừng phá.

Chúng ở vị trí khác nhau trên đường thẳng ngoài trang trại. FJ biết vị trí $P_i$ của từng bò $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ so với cổng (vị trí $0$), nơi bắt đầu.

FJ đi một đơn vị mỗi phút, buộc cương ngay lập tức. Xác định thứ tự thăm giảm tổng thiệt hại và tính tổng nhỏ nhất.

Dữ liệu vào

• Dòng $1$: số bò $N$.

• Dòng $2..N+1$: dòng $i+1$ có số nguyên $P_i$.

Dữ liệu ra

• Dòng $1$: tổng thiệt hại nhỏ nhất.

Ví dụ

Dữ liệu vào 1

4
-2
-12
3
7

Dữ liệu ra 1

50

Ghi chú

Bốn bò ở $-2$, $-12$, $3$, $7$.

Thứ tự tối ưu $-2$, $3$, $7$, $-12$. Tới $-2$ sau $2$ phút, bò đó hại $2$ đô la.

Tới $3$ (khoảng cách $5$): bò đó hại $2 + 5 = 7$ đô la.

Thêm $4$ phút tới $7$: $7 + 4 = 11$ đô la.

Cuối cùng $19$ phút tới $-12$: $11 + 19 = 30$ đô la.

Tổng $2 + 7 + 11 + 30 = 50$ đô la.

Tác giả bài toán: Chris Tzamos, 2006