시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1101 347 275 33.414%

문제

정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러번 더해도 된다)

수열이 주어졌을 때, 총 몇 개의 수가 좋은 수 일까?

입력

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 5000) 둘째 줄에는 수열 A의 각 숫자가 공백으로 구분되어 주어진다. (-100,000 ≤ Ai ≤ 100,000)

출력

첫째 줄에 좋은 수의 개수를 출력한다.

예제 입력 1

6
1 2 3 5 7 10

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjU2MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4OGJcdWM3NDAgXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM4MTVcdWMyMTggTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0IEFcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIGlcdWJjODhcdWM5ZjggXHVjMjE4XHVhYzAwIFx1YWRmOCBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWMyMThcdWI5N2MgXHVjODhiXHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gKFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWM1ZWNcdWI3ZWNcdWJjODggXHViMzU0XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2QxZCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4OGJcdWM3NDAgXHVjMjE4IFx1Yzc3Y1x1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0IEFcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA1MDAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YWMwMSBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMTAwLDAwMCAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzg4Ylx1Yzc0MCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjI0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRE9CUkkiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBzZXF1ZW5jZSBBIGNvbnNpc3Rpbmcgb2YgTiBpbnRlZ2VycyAobm90IHRvIGJlIGNvbmZ1c2VkIHdpdGggdGhlIHNlcXVlbmNlIGZyb20gdGhlIHByZXZpb3VzIHRhc2spLiBXZSB3aWxsIGNhbGwgdGhlIGk8c3VwPnRoPFwvc3VwPiBzZXF1ZW5jZSBlbGVtZW50IGdvb2QgaWYgaXQgZXF1YWxzIHRoZSBzdW0gb2Ygc29tZSB0aHJlZSBlbGVtZW50cyBpbiBwb3NpdGlvbnMgc3RyaWN0bHkgc21hbGxlciB0aGFuIGkgKGFuIGVsZW1lbnQgY2FuIGJlIHVzZWQgbW9yZSB0aGFuIG9uY2UgaW4gdGhlIHN1bSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhvdyBtYW55IGdvb2QgZWxlbWVudHMgZG9lcyB0aGUgc2VxdWVuY2UgY29udGFpbj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgNTAwMCksIHRoZSBsZW5ndGggb2YgdGhlIHNlcXVlbmNlIEEuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyByZXByZXNlbnRpbmcgdGhlIHNlcXVlbmNlIEEgKC0xMDAgMDAwICZsZTsgQTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAgMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBudW1iZXIgb2YgZ29vZCBlbGVtZW50cyBpbiB0aGUgc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==