“Hãy khôn ngoan trong kinh doanh” Hãy xem Bờm đã vận dụng thế nào? Cậu ấy đã nợ hoặc tạm ứng cho các khách hàng, có \(N\) khách để thuận tiện đánh số từ \(1\) đến \(N\).

Ngày kết thúc cuối cùng đã đến. Cậu ấy biết không thể trả khi không có đủ tiền. Có tất cả \(N\) khách hàng xếp theo một đường thẳng với khoảng cách đều nhau \(1\) đơn vị. Bờm sẽ thu tiền người nợ và sẽ trả cho khách mình đang nợ khi số tiền đủ trả, không nhất thiết nhận hết rồi mới trả nhưng luôn về đích khi kết thúc.

Khi cậu di chuyển tới, người nợ sẽ trả, và khi có đủ cậu sẽ trả cho các người mình nợ. Người \(i\) nợ Bờm \(D_i\) tiền. Dấu trừ (\(-\)) có nghĩa là Bờm nợ tiền.

Bờm bắt đầu ở vị trí \(0\) và phải kết thúc chuyến đi của mình ở vị trí người cuối cùng. Hãy tính quãng đường ngắn nhất mà cậu ấy phải đi để thu tiền nợ và trả tất cả những người cậu ấy nợ? Trường hợp không đủ tiền trả thì Bờm sẽ quay vị trí cuối và vẫn còn nợ.

Input

• Dòng \(1\) là một số nguyên \(N (1 \le N \le 10^5)\);
• \(N\) dòng kế tiếp mỗi dòng chứa số nguyên \(D_i\) \((-10^3 \le D_i \le 10^3)\).

Output

• Có một số nguyên duy nhất là quãng đường tối thiểu phải đi theo yêu cầu.

Example

5
100
-200
250
-200
150

9