시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB71517711331.742%

문제

민균이와 상범이는 오래된 연인이다.

요즘따라 냉랭해진 상범이의 태도를 본 민균이는 상범이의 기분을 예측한 다음, 상범이가 우울해지기 전에 꽃을 선물함으로써 그의 기분을 상큼하게 만들어주려고 한다.

상범이의 기분은 하루씩 정수로 표현되는데, 기분이 좋은 날은 양수로 표현되고 우울한 날은 음수로 표현된다. (따라서 음수만 나타나는 연속적인 구간을 '우울한 기간' 또는 '우울 기간'이라고 한다)

한편, 상범이의 우울 기간의 길이가 T일 땐, 구간의 시작으로부터 2T일 전부터 구간의 시작 바로 전날까지 꽃을 선물해야 그의 우울함을 덜어줄 수 있다. 주의해야 할 점은 길이가 가장 긴 우울 구간의 경우에는 2T일 이전이 아닌 3T일 이전부터 꽃을 선물해야 한다는 점이다. 현재부터 가장 빠른 상범이의 우울기간을 T_f 라고 하자. 만약 현재부터 계속해서 꽃을 선물해도 가장 빠른 상범이의 우울기간까지 2 * T_f 만큼 꽃을 선물할 수 없다고 하더라고 줄 수 있는만큼 꽃을 줘야 한다. (단, 이런 최장 우울 구간이 여러 개인 경우에는 그중 한 구간만 이렇게 하면 되고, 나머지 구간은 2T로 적용하면 된다)

민균이가 예측한 앞으로 N일간의 상범이의 기분이 주어졌을 때, 이 N일 중 그가 상범이에게 꽃을 줘야하는 날의 수(사야 하는 꽃의 개수)의 최댓값을 구해보자.

입력

첫 번째 줄에는 예측한 날의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

두 번째 줄에는 상범이의 기분을 나타내는 N개의 정수(|기분| ≤ 100)가 주어진다.

출력

민균이가 상범이에게 꽃을 주어야하는 날의 최댓값을 출력한다.

예제 입력 1

8
1 -1 4 3 8 -2 3 -3

예제 출력 1

6

예제 입력 2

15
1 2 -1 2 3 4 5 6 1 4 8 3 -1 -2 1

예제 출력 2

8
W3sicHJvYmxlbV9pZCI6IjI4MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWJjOTRcdWM3NzRcdWM3NTggXHVjNmIwXHVjNmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiZmNcdWFkZTBcdWM3NzRcdWM2NDAgXHVjMGMxXHViYzk0XHVjNzc0XHViMjk0IFx1YzYyNFx1Yjc5OFx1YjQxYyZuYnNwO1x1YzVmMFx1Yzc3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjk0XHVjOTk4XHViNTMwXHViNzdjIFx1YjBjOVx1YjdhZFx1ZDU3NFx1YzljNCBcdWMwYzFcdWJjOTRcdWM3NzRcdWM3NTggXHVkMGRjXHViM2M0XHViOTdjIFx1YmNmOCZuYnNwO1x1YmJmY1x1YWRlMFx1Yzc3NFx1YjI5NCBcdWMwYzFcdWJjOTRcdWM3NzRcdWM3NTggXHVhZTMwXHViZDg0XHVjNzQ0IFx1YzYwOFx1Y2UyMVx1ZDU1YyBcdWIyZTRcdWM3NGMsJm5ic3A7XHVjMGMxXHViYzk0XHVjNzc0XHVhYzAwIFx1YzZiMFx1YzZiOFx1ZDU3NFx1YzljMFx1YWUzMCBcdWM4MDRcdWM1ZDAmbmJzcDtcdWFmNDNcdWM3NDQgXHVjMTIwXHViYjNjXHVkNTY4XHVjNzNjXHViODVjXHVjMzY4IFx1YWRmOFx1Yzc1OCBcdWFlMzBcdWJkODRcdWM3NDQgXHVjMGMxXHVkMDdjXHVkNTU4XHVhYzhjIFx1YjljY1x1YjRlNFx1YzViNFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YmM5NFx1Yzc3NFx1Yzc1OCBcdWFlMzBcdWJkODRcdWM3NDAgXHVkNTU4XHViOGU4XHVjNTI5Jm5ic3A7XHVjODE1XHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YjI5NFx1YjM3MCwgXHVhZTMwXHViZDg0XHVjNzc0IFx1Yzg4Ylx1Yzc0MCBcdWIwYTBcdWM3NDAgXHVjNTkxXHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YWNlMCBcdWM2YjBcdWM2YjhcdWQ1NWMgXHViMGEwXHVjNzQwIFx1Yzc0Y1x1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MWNcdWIyZTQuIChcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzRjXHVjMjE4XHViOWNjIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YjI5NCBcdWM1ZjBcdWMxOGRcdWM4MDFcdWM3NzggXHVhZDZjXHVhYzA0XHVjNzQ0ICYjMzk7XHVjNmIwXHVjNmI4XHVkNTVjIFx1YWUzMFx1YWMwNCYjMzk7IFx1YjYxMFx1YjI5NCAmIzM5O1x1YzZiMFx1YzZiOCBcdWFlMzBcdWFjMDQmIzM5O1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1ZDU1Y1x1ZDNiOCwgXHVjMGMxXHViYzk0XHVjNzc0XHVjNzU4IFx1YzZiMFx1YzZiOCBcdWFlMzBcdWFjMDRcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFRcdWM3N2MgXHViNTUwLCBcdWFkNmNcdWFjMDRcdWM3NTggXHVjMmRjXHVjNzkxXHVjNzNjXHViODVjXHViZDgwXHVkMTMwIDJUXHVjNzdjIFx1YzgwNFx1YmQ4MFx1ZDEzMCBcdWFkNmNcdWFjMDRcdWM3NTggXHVjMmRjXHVjNzkxIFx1YmMxNFx1Yjg1YyBcdWM4MDRcdWIwYTBcdWFlNGNcdWM5YzAgXHVhZjQzXHVjNzQ0IFx1YzEyMFx1YmIzY1x1ZDU3NFx1YzU3YyBcdWFkZjhcdWM3NTggXHVjNmIwXHVjNmI4XHVkNTY4XHVjNzQ0IFx1YjM1Y1x1YzViNFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM4ZmNcdWM3NThcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1YzgxMFx1Yzc0MCBcdWFlMzhcdWM3NzRcdWFjMDAmbmJzcDtcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YzZiMFx1YzZiOCBcdWFkNmNcdWFjMDRcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDJUXHVjNzdjIFx1Yzc3NFx1YzgwNFx1Yzc3NCBcdWM1NDRcdWIyY2MgM1RcdWM3N2MgXHVjNzc0XHVjODA0XHViZDgwXHVkMTMwIFx1YWY0M1x1Yzc0NCBcdWMxMjBcdWJiM2NcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0XHViMjk0IFx1YzgxMFx1Yzc3NFx1YjJlNC4gXHVkNjA0XHVjN2FjXHViZDgwXHVkMTMwIFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMGMxXHViYzk0XHVjNzc0XHVjNzU4IFx1YzZiMFx1YzZiOFx1YWUzMFx1YWMwNFx1Yzc0NCBUX2YgXHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHViOWNjXHVjNTdkIFx1ZDYwNFx1YzdhY1x1YmQ4MFx1ZDEzMCBcdWFjYzRcdWMxOGRcdWQ1NzRcdWMxMWMgXHVhZjQzXHVjNzQ0IFx1YzEyMFx1YmIzY1x1ZDU3NFx1YjNjNCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzBjMVx1YmM5NFx1Yzc3NFx1Yzc1OCBcdWM2YjBcdWM2YjhcdWFlMzBcdWFjMDRcdWFlNGNcdWM5YzAgMiAqIFRfZiBcdWI5Y2NcdWQwN2MgXHVhZjQzXHVjNzQ0IFx1YzEyMFx1YmIzY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0XHVhY2UwIFx1ZDU1OFx1YjM1NFx1Yjc3Y1x1YWNlMCBcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjljY1x1ZDA3YyBcdWFmNDNcdWM3NDQgXHVjOTE4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4mbmJzcDsoXHViMmU4LCBcdWM3NzRcdWI3ZjAgXHVjZDVjXHVjN2E1IFx1YzZiMFx1YzZiOCBcdWFkNmNcdWFjMDRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZGY4XHVjOTExIFx1ZDU1YyBcdWFkNmNcdWFjMDRcdWI5Y2MgXHVjNzc0XHViODA3XHVhYzhjIFx1ZDU1OFx1YmE3NCBcdWI0MThcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWFkNmNcdWFjMDRcdWM3NDAgMlRcdWI4NWMgXHVjODAxXHVjNmE5XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHViYmZjXHVhZGUwXHVjNzc0XHVhYzAwIFx1YzYwOFx1Y2UyMVx1ZDU1YyBcdWM1NWVcdWM3M2NcdWI4NWMgTlx1Yzc3Y1x1YWMwNFx1Yzc1OCBcdWMwYzFcdWJjOTRcdWM3NzRcdWM3NTggXHVhZTMwXHViZDg0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCZuYnNwO05cdWM3N2MgXHVjOTExJm5ic3A7XHVhZGY4XHVhYzAwJm5ic3A7XHVjMGMxXHViYzk0XHVjNzc0XHVjNWQwXHVhYzhjIFx1YWY0M1x1Yzc0NCBcdWM5MThcdWM1N2NcdWQ1NThcdWIyOTQgXHViMGEwXHVjNzU4IFx1YzIxOChcdWMwYWNcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWY0M1x1Yzc1OCBcdWFjMWNcdWMyMTgpXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2MDhcdWNlMjFcdWQ1NWMgXHViMGEwXHVjNzU4IFx1YzIxOCZuYnNwO04gKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWJjOTRcdWM3NzRcdWM3NTggXHVhZTMwXHViZDg0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCh8XHVhZTMwXHViZDg0fCZuYnNwOyZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYmZjXHVhZGUwXHVjNzc0XHVhYzAwIFx1YzBjMVx1YmM5NFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWFmNDNcdWM3NDQgXHVjOGZjXHVjNWI0XHVjNTdjXHVkNTU4XHViMjk0IFx1YjBhMFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJaSU1BIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgb2xkIHRpbWVzLCB3aGVuIGRyYWdvbnMgcnVsZWQgdGhlIGxhbmQsIGFpciB0ZW1wZXJhdHVyZSBuZXZlciBmZWxsIGJlbG93IHplcm8gZGVncmVlcy4gQnV0IGFmdGVyIGRyYWdvbnMgbGVmdCwgbmljZSBhbmQgd2FybSB0aW1lcyB3ZW50IHdpdGggdGhlbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Ugc2F5IHRoYXQgZGF5IGlzIGEgd2ludGVyIGRheSB3aGVuIGF2ZXJhZ2UgdGVtcGVyYXR1cmUgZm9yIHRoYXQgZGF5IGlzIGJlbG93IHplcm8uIFdlIHNheSB0aGF0IFQgY29uc2VjdXRpdmUgd2ludGVyIGRheXMgZm9ybSBhIHdpbnRlciBwZXJpb2Qgb2YgbGVuZ3RoIFQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBzb21lIHBlb3BsZSB0aGF0IGFubm95IGV2ZXJ5b25lIGJ5IHJhbWJsaW5nIG9uIGFib3V0IHNvbWUgd2ludGVyIHRoYXQgaXMgY29taW5nLiBTbyBhIGxhdyBoYWQgdG8gYmUgbWFkZSwgc3RhdGluZyB0aGF0IHlvdSBhcmUgYWxsb3dlZCB0byBzYXkgdGhhdCB3aW50ZXIgaXMgY29taW5nIGF0IG1vc3QgMlQgZGF5cyBiZWZvcmUgYSB3aW50ZXIgcGVyaW9kIG9mIGxlbmd0aCBULiBFeGNlcHRpb24gdG8gdGhpcyBpcyBvbmx5IHRoZSB3aW50ZXIgcGVyaW9kIHdpdGggdGhlIGxvbmdlc3QgbGVuZ3RoLCB0aGF0IGNhbiBiZSBhbm5vdW5jZWQgYXQgbW9zdCAzVCBkYXlzIGJlZm9yZSBpdCBiZWdpbnMuIER1cmluZyBzb21lIHdpbnRlciBwZXJpb2QsIHlvdSBjYW4mcnNxdW87dCBzYXkgdGhhdCB0aGlzIHBlcmlvZCBpcyBjb21pbmcsIHNpbmNlIGl0JnJzcXVvO3MgYWxyZWFkeSBoZXJlLCBidXQgeW91IGNhbiBhbm5vdW5jZSBmdXR1cmUgd2ludGVyIHBlcmlvZHMgYWNjb3JkaW5nIHRvIHRoZXJ1bGVzIGFib3ZlLiBJZiB0aGVyZSBhcmUgbW9yZSB0aGFuIG9uZSB3aW50ZXIgcGVyaW9kcyB3aXRoIHRoZSBsb25nZXN0IGxlbmd0aCwgdGhlbiBvbmx5IG9uZSBpcyBjaG9zZW4gYW5kIDNUIGRheXMgcnVsZSBpcyBhcHBsaWVkIG9ubHkgdG8gdGhhdCBwZXJpb2QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPktub3dpbmcgZXhwZWN0ZWQgdGVtcGVyYXR1cmVzIGZvciBzb21lIHRpbWUgcGVyaW9kLCBmaW5kIG91dCB0aGUgbWF4aW11bSBudW1iZXIgb2YgZGF5cyBkdXJpbmcgd2hpY2ggaXQgaXMgYWxsb3dlZCB0byBzYXkgdGhhdCB3aW50ZXIgaXMgY29taW5nLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgbGVuZ3RoIG9mIHRoZSBvdmVyYWxsIHRpbWUgcGVyaW9kIHdlIGFyZSBjb25zaWRlcmluZy4gVGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMsIHRlbXBlcmF0dXJlcyBvZiBjb25zZWN1dGl2ZSBkYXlzIGluIGNvbnNpZGVyZWQgcGVyaW9kLiBBYnNvbHV0ZSB2YWx1ZXMgb2YgdGhlc2UgaW50ZWdlcnMgd29uJnJzcXVvO3QgZXhjZWVkIDEwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIG1heGltdW0gbnVtYmVyIG9mIGRheXMgZHVyaW5nIHdoaWNoIGl0IGlzIGFsbG93ZWQgdG8gYW5ub3VuY2UgdGhlIHdpbnRlciBpcyBjb21pbmcuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #4 2번