시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 162 27 15 28.846%

문제

월스트리트에는 n개의 은행이있다. 모든 은행은 양 옆으로 이웃하는 은행이 하나씩 있으며, 첫번째 은행의 왼쪽에는 마지막 은행이있고, 마지막은행의 오른쪽에는 첫번째 은행이있다(원형으로 나열되있다). 각 은행은 K만큼의 자본이 있고 모든 은행 자본의 합은 양수이다.

i번 은행의 자본, K(i)가 음수일 경우, 은행 요정은 이 자본을 양수로 만들어줄수있다. 예를들어, 자본이 -7일경우, 요정의 힘을 빌린 후에는 자본이 7이된다. 그러나 요정의 힘을 사용하면 이웃하는 양 옆 은행은 i은행 자본의 절댓값만큼 손해를 본다. i은행의 양옆 이웃은행의 자본이 5와 11이라면 -2와 4로 줄어든다.

모든 은행의 자본을 0 또는 양수로 만들기 위해 요정의 힘을 빌려야할 최소 횟수는 얼마일까?

입력

첫번째 줄에는 은행 갯수 n이 주어진다. (0 < n < 10000)

두번째 줄에는 각 은행의 자본 k(i)가 순서대로 주어진다. (-32000 < k(i) < 32000)

각 자본은 한칸의 공백을 두고 주어진다.

출력

요정의 힘을 빌려야할 최소 횟수를 출력한다.

예제 입력 1

4
1 -2 -1 3

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjEwMzUwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzQwXHVkNTg5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2ZDRcdWMyYTRcdWQyYjhcdWI5YWNcdWQyYjhcdWM1ZDBcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWM3NDBcdWQ1ODlcdWM3NzRcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM3NDBcdWQ1ODlcdWM3NDAgXHVjNTkxIFx1YzYwNlx1YzczY1x1Yjg1YyBcdWM3NzRcdWM2YzNcdWQ1NThcdWIyOTQgXHVjNzQwXHVkNTg5XHVjNzc0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM3NDBcdWQ1ODlcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWM3NDBcdWQ1ODlcdWM3NzRcdWM3ODhcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOVx1Yzc0MFx1ZDU4OVx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDBcdWIyOTQgXHVjY2FiXHViYzg4XHVjOWY4IFx1Yzc0MFx1ZDU4OVx1Yzc3NFx1Yzc4OFx1YjJlNChcdWM2ZDBcdWQ2MTVcdWM3M2NcdWI4NWMgXHViMDk4XHVjNWY0XHViNDE4XHVjNzg4XHViMmU0KS4gXHVhYzAxIFx1Yzc0MFx1ZDU4OVx1Yzc0MCBLXHViOWNjXHVkMDdjXHVjNzU4IFx1Yzc5MFx1YmNmOFx1Yzc3NCBcdWM3ODhcdWFjZTAgXHViYWE4XHViNGUwIFx1Yzc0MFx1ZDU4OSBcdWM3OTBcdWJjZjhcdWM3NTggXHVkNTY5XHVjNzQwIFx1YzU5MVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+aVx1YmM4OCBcdWM3NDBcdWQ1ODlcdWM3NTggXHVjNzkwXHViY2Y4LCBLKGkpXHVhYzAwIFx1Yzc0Y1x1YzIxOFx1Yzc3YyBcdWFjYmRcdWM2YjAsIFx1Yzc0MFx1ZDU4OSBcdWM2OTRcdWM4MTVcdWM3NDAgXHVjNzc0IFx1Yzc5MFx1YmNmOFx1Yzc0NCBcdWM1OTFcdWMyMThcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOTA0XHVjMjE4XHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2NcdWI0ZTRcdWM1YjQsIFx1Yzc5MFx1YmNmOFx1Yzc3NCAtN1x1Yzc3Y1x1YWNiZFx1YzZiMCwgXHVjNjk0XHVjODE1XHVjNzU4IFx1ZDc5OFx1Yzc0NCBcdWJlNGNcdWI5YjAgXHVkNmM0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YmNmOFx1Yzc3NCA3XHVjNzc0XHViNDFjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVjNjk0XHVjODE1XHVjNzU4IFx1ZDc5OFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQgXHVjNzc0XHVjNmMzXHVkNTU4XHViMjk0IFx1YzU5MSBcdWM2MDYgXHVjNzQwXHVkNTg5XHVjNzQwIGlcdWM3NDBcdWQ1ODkgXHVjNzkwXHViY2Y4XHVjNzU4IFx1YzgwOFx1YjMxM1x1YWMxMlx1YjljY1x1ZDA3YyBcdWMxOTBcdWQ1NzRcdWI5N2MgXHViY2Y4XHViMmU0LiBpXHVjNzQwXHVkNTg5XHVjNzU4IFx1YzU5MVx1YzYwNiBcdWM3NzRcdWM2YzNcdWM3NDBcdWQ1ODlcdWM3NTggXHVjNzkwXHViY2Y4XHVjNzc0IDVcdWM2NDAgMTFcdWM3NzRcdWI3N2NcdWJhNzQgLTJcdWM2NDAgNFx1Yjg1YyBcdWM5MDRcdWM1YjRcdWI0ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3NDBcdWQ1ODlcdWM3NTggXHVjNzkwXHViY2Y4XHVjNzQ0IDAgXHViNjEwXHViMjk0IFx1YzU5MVx1YzIxOFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzY5NFx1YzgxNVx1Yzc1OCBcdWQ3OThcdWM3NDQgXHViZTRjXHViODI0XHVjNTdjXHVkNTYwIFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWIyOTQgXHVjNWJjXHViOWM4XHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NDBcdWQ1ODkgXHVhYzJmXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IG4gJmx0OyAxMDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjNzQwXHVkNTg5XHVjNzU4IFx1Yzc5MFx1YmNmOCBrKGkpXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMzIwMDAgJmx0OyBrKGkpICZsdDsgMzIwMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM3OTBcdWJjZjhcdWM3NDAgXHVkNTVjXHVjZTc4XHVjNzU4IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzY5NFx1YzgxNVx1Yzc1OCBcdWQ3OThcdWM3NDQgXHViZTRjXHViODI0XHVjNTdjXHVkNTYwIFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMzUwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFua3MiLCJkZXNjcmlwdGlvbiI6IjxwPk9uIFdhbGwgU3RyZWV0IGZyb20gV29uZGVybGFuZCwgd2UgaGF2ZSBuIGJhbmtzLCB3aXRoIDEwMDAwICZndDsgbiAmZ3Q7IDAuIEVhY2ggYmFuayBoYXMgZXhhY3RseSB0d28gbmVpZ2hib3VycywgdGhlIGxlZnQgKEwpIGFuZCByaWdodCAoUikgbmVpZ2hib3VyLiBUaGUgZmlyc3QgYmFuayZyc3F1bztzIGxlZnQgbmVpZ2hib3VyIGlzIHRoZSBsYXN0IGJhbmssIHdoaWxlIHRoZSBsYXN0IGJhbmsmcnNxdW87cyByaWdodCBuZWlnaGJvdXIgaXMgdGhlIGZpcnN0IGJhbmsuIEVhY2ggYmFuayBpKG4mZ3Q7aSZnZTswKSBoYXMgYSBjYXBpdGFsIGs8c3ViPmk8XC9zdWI+IHdpdGggMzIwMDAmZ3Q7azxzdWI+aTxcL3N1Yj4mZ3Q7LTMyMDAwLiBUaGUgZW50aXJlIGNhcGl0YWwgb2YgYWxsIGJhbmtzIHB1dCB0b2dldGhlciBpcyBrbm93biB0byBiZSBwb3NpdGl2ZS4gV2hlbmV2ZXIgc29tZSBjYXBpdGFsIGs8c3ViPmk8XC9zdWI+IG9mIGJhbmsgaSBpcyBuZWdhdGl2ZSwgdGhlIEJhbmsgRmFpcnkgY2FuIGRvIGEgbWFnaWMgbW92ZSBhbmQgdHVybiB0aGUgY2FwaXRhbCBpbnRvIGEgcG9zaXRpdmUgb25lLiBGb3IgaW5zdGFuY2UsIGlmIGs8c3ViPmk8XC9zdWI+PS03LCBhZnRlciB0aGUgbWFnaWMgbW92ZSwgazxzdWI+aTxcL3N1Yj49Ny4gVW5mb3J0dW5hdGVseSwgdGhlIG1hZ2ljIG1vdmUgaGFzIGNvbnNlcXVlbmNlcyBmb3IgYm90aCBuZWlnaGJvdXJzIG9mIGJhbmsgaS4gRWFjaCBzZWVzIGl0cyBjYXBpdGFsIHJlZHVjZWQgd2l0aCB0aGUgYWJzb2x1dGUgdmFsdWUgb2YgdGhlIGNhcGl0YWwgb2YgYmFuayBpLiBGb3IgaW5zdGFuY2UgaWYgYmFuayBMIGhhcyBjYXBpdGFsIGs8c3ViPkw8XC9zdWI+PTUgYW5kIGJhbmsgUiBoYXMgY2FwaXRhbCBrPHN1Yj5SPFwvc3ViPj0xMSwgdGhlbiBhZnRlciB0aGUgbWFnaWMgbW92ZSBrPHN1Yj5MPFwvc3ViPj0tMiBhbmQgazxzdWI+UjxcL3N1Yj49NC48XC9wPlxyXG5cclxuPHA+V2hpY2ggaXMgdGhlIG1pbmltYWwgbnVtYmVyIG9mIG1hZ2ljIG1vdmVzIHdoaWNoIHRoZSBCYW5rIEZhaXJ5IGhhcyB0byBkbyBpbiBvcmRlciB0byBtYWtlIHRoZSBjYXBpdGFsIG9mIGFsbCBiYW5rcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gMD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBpbnB1dCBsaW5lLCB3ZSBoYXZlIHRoZSBudW1iZXIgbiBvZiBiYW5rcy4gT24gdGhlIHNlY29uZCBpbnB1dCBsaW5lLCB3ZSBoYXZlIHRoZSBjYXBpdGFscyBrPHN1Yj5pPFwvc3ViPihuJmd0O2kmZ2U7MCkgb2YgYWxsIGJhbmtzLCBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSBhcmUgZm91bmQgb24gV2FsbCBTdHJlZXQgZnJvbSBXb25kZXJsYW5kLiBFYWNoIGNhcGl0YWwgaXMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHdoaXRlc3BhY2UgZnJvbSB0aGUgbmV4dCBvbmUsIGV4Y2VwdCBmb3IgdGhlIGZpbmFsIGNhcGl0YWwgd2hpY2ggaXMgZGlyZWN0bHkgZm9sbG93ZWQgYnkgdGhlIG5ld2xpbmUgY2hhcmFjdGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgY29udGFpbnMgYSBzaW5nbGUgbGluZSB3aXRoIHRoZSB2YWx1ZSBvZiB0aGUgbWluaW1hbCBudW1iZXIgb2YgbWFnaWMgbW92ZXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==