빚 청산

Bessie는 $N$($1 \le N \le 100000$)명의 친구 각각과 돈을 빌리거나 빌려주었습니다. 친구에게는 $1$부터 $N$까지 번호가 매겨져 있습니다.

드디어 빚을 갚는 날이 되었습니다. Bessie가 받을 돈의 합이 갚아야 할 돈의 합보다 많습니다. 친구들은 일직선으로 서 있으며, $i$번 친구는 헛간에서 $i$미터 떨어진 곳에 서 있습니다. Bessie는 헛간(위치 $0$)에서 출발해 줄을 따라 걸으며, 자신에게 빚진 친구에게서 돈을 받고, 자신이 빚진 친구에게 돈을 갚습니다.

각 친구 $i$에는 정수 $D_i$($-1000 \le D_i \le 1000$, $D_i \ne 0$)가 주어집니다. $D_i > 0$이면 $i$번 친구가 Bessie에게 $D_i$만큼 빚진 것이고, $D_i < 0$이면 Bessie가 $i$번 친구에게 $|D_i|$만큼 빚진 것입니다.

Bessie는 자신에게 빚진 친구를 지날 때 그 돈을 즉시 받을 수 있습니다. 하지만 자신이 빚진 친구에게는 현재 들고 있는 현금이 갚을 금액 이상일 때에만 갚을 수 있습니다(들고 있는 현금은 결코 음수가 될 수 없습니다). 어떤 친구에게 처음 도착했을 때 갚을 현금이 부족할 수 있으므로, 그 친구를 지나쳐 더 앞에서 돈을 받은 뒤 다시 돌아와 갚아야 할 수도 있습니다.

Bessie는 헛간(위치 $0$)에서 출발하여 줄의 맨 끝(위치 $N$)에서 여정을 마쳐야 합니다. 모든 거래를 끝내기 위해 이동해야 하는 최소 총 거리는 얼마입니까?

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 정수 $D_i$가 주어집니다.

• 첫째 줄: Bessie가 모든 친구에게서 돈을 받고 갚기 위해 이동해야 하는 최소 총 거리를 나타내는 정수 하나.

예시에서 다섯 친구는 위치 $1$부터 $5$까지 서 있고, 각각의 값은 $100, -200, 250, -200, 200$입니다.

• 헛간에서 오른쪽으로 걸어 $1$번 친구에게서 $100$을 받습니다(현재 $100$).
• $2$번 친구에게는 $200$을 갚아야 하지만 현재 $100$뿐이므로 지나칩니다. $3$번 친구까지 가서 $250$을 받습니다(현재 $350$).
• 다시 $2$번 친구에게 돌아와 $200$을 갚습니다(현재 $150$).
• 다시 오른쪽으로 걸어 $4$번 친구($200$을 갚아야 하지만 현재 $150$뿐)를 지나치고 $5$번 친구에게서 $200$을 받습니다(현재 $350$).
• $4$번 친구에게 돌아와 $200$을 갚고(현재 $150$), 줄의 맨 끝으로 돌아와 여정을 마칩니다.

이동 거리는 $3 + 1 + 3 + 1 + 1 = 9$입니다.