“빌리지도 빌려주지도 마라.” Bessie는 그 조언을 따랐더라면 하고 후회합니다! $N$명, $(1 \le N \le 100,000)$ 친구 각각과 돈을 빌리거나 빌려줬으며 번호는 $1,\ldots,N$입니다.

갚는 날입니다. 받을 돈이 갚을 돈보다 많습니다. 소는 직선에 서서 소 $i$는 헛간에서 $i$미터입니다. Bessie는 걸으며 돈을 받고 갚습니다.

돈을 빌린 소에게 갚으라 요청할 수 있습니다. 일부나 모든 빚을 갚을 돈이 충분하면 방금 받은 돈으로 갚습니다. 소 $i$가 Bessie에게 $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