Farmer John quên sửa lỗ trên hàng rào, nên $N$ bò $(1 \le N \le 1,000)$ trốn ra và phá phách! Mỗi phút ngoài rào, một bò gây thiệt hại một đô la. FJ phải đến từng bò và đeo dây cương để nó bình tĩnh, ngừng gây thiệt hại.

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

FJ đi một đơn vị khoảng cách mỗi phút và đeo dây cương ngay lập tức. Hãy xác định thứ tự thăm bò để tổng thiệt hại nhỏ nhất, và tính tổng nhỏ nhất đó.

Dữ liệu vào

• Dòng 1: số bò $N$.
• Dòng $2\ldots 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ò ở các vị trí $-2$, $-12$, $3$ và $7$.

Thứ tự tối ưu là $-2,3,7,-12$. FJ đến $-2$ sau 2 phút, nên bò đó gây thiệt hại 2 đô la.

Sau đó đi đến $3$ (khoảng cách 5), thiệt hại tích lũy của bò đó là $2 + 5 = 7$ đô la.

Ông mất thêm 4 phút đến $7$, với thiệt hại $7 + 4 = 11$ đô la của bò đó.

Cuối cùng mất 19 phút đến $-12$, với thiệt hại $11 + 19 = 30$ đô la.

Tổng thiệt hại là $2 + 7 + 11 + 30 = 50$ đô la.

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