Farmer John שכח לתקן חור בגדר החווה, ו־$N$ הפרות שלו $(1 \le N \le 1,000)$ ברחו ומשתוללות! כל דקה מחוץ לגדר, כל פרה גורמת נזק בשווי דולר אחד. FJ חייב לבקר כל פרה ולשים לה רסן שירגיע אותה ויעצור את הנזק.
למרבה המזל, הפרות במיקומים שונים על קו ישר בכביש מחוץ לחווה. FJ יודע את מיקום $P_i$ של כל פרה $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ ביחס לשער (מיקום 0) שבו הוא מתחיל.
FJ נע יחידת מרחק אחת בדקה ויכול לשים רסן מיד. קבעו סדר ביקורים שממזער את עלות הנזק הכוללת וחשבו את העלות המזערית הזאת.
קלט
- שורה 1: מספר הפרות $N$.
- שורות $2\ldots N+1$: שורה $i+1$ מכילה את השלם $P_i$.
פלט
- שורה 1: עלות הנזק הכוללת המזערית.
דוגמאות
קלט 1
4 -2 -12 3 7
פלט 1
50
הערה
ארבע פרות במיקומים $-2$, $-12$, $3$, $7$.
סדר הביקור המיטבי הוא $-2,3,7,-12$. FJ מגיע ל־$-2$ בתוך 2 דקות, והפרה הזאת גורמת נזק של 2 דולרים.
אז הוא הולך ל־$3$ (מרחק 5), שם הנזק המצטבר של הפרה הוא $2 + 5 = 7$ דולרים.
הוא צריך עוד 4 דקות להגיע ל־$7$, בנזק $7 + 4 = 11$ דולרים מהפרה הזאת.
לבסוף הוא צריך 19 דקות להגיע ל־$-12$, בעלות $11 + 19 = 30$ דולרים.
הנזק הכולל הוא $2 + 7 + 11 + 30 = 50$ דולרים.
מחבר הבעיה: Chris Tzamos, 2006