«لا تكن مقترضًا ولا مقرضًا». كم تتمنى Bessie لو اتبعت النصيحة! اقترضت من أو أقرضت كل واحد من $N$ أصدقاء، $(1 \le N \le 100,000)$، مرقمين $1,\ldots,N$.

جاء يوم السداد. لها أكثر مما عليها للآخرين. الأبقار في خط مستقيم، البقرة $i$ تبعد $i$ مترًا عن الحظيرة. ستسير لتحصيل ما لها وسداد ما عليها.

يمكن أن تطلب السداد من أي مدينة لها. إذا كفى المال لبعض أو كل ديونها، تدفع المحصل حديثًا للدائنات. البقرة $i$ مدينة لها بـ$D_{i}$، $(-1,000 \le D_{i} \le 1,000; D_{i} \ne 0)$. السالب يعني أن Bessie مدينة للبقرة بالعكس.

تبدأ بالحظيرة، الموقع 0. ما أقل مسافة لتحصيل الكل وسداد الكل؟ يجب أن تنتهي بنهاية الصف.

الإدخال

• السطر 1: الصحيح $N$.
• الأسطر $2,\ldots,N+1$: السطر $i+1$ يحتوي الصحيح $D_{i}$.

الإخراج

• السطر 1: صحيح، المسافة الإجمالية بالأمتار لتحصيل أو دفع مال كل بقرة.

أمثلة

الإدخال 1

5
100
-200
250
-200
200

الإخراج 1

9

ملاحظة

ثلاث بقرات مدينة لـBessie، وهي مدينة لاثنتين. تنتهي ومعها 150 مالًا.

      100  -200  250 -200  200
 |     |     |    |    |    |
 ***>**+**>*****>**+
                   *            < لدى Bessie 350
             -**<***
             *                  < لدى Bessie 150
             ***>****>****>**+
                             *  < لدى Bessie 350
                       -**<***
                       *     
                       ***>***  < تنهي Bessie ومعها 150*

يسارًا: الحظيرة.

مؤلف المسألة: Jarrah Lacko، 2009