시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 988 310 242 34.085%

문제

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

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

입력

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

출력

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

예제 입력 1

6
1 2 3 5 7 10

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjU2MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4OGJcdWM3NDAgXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM4MTVcdWMyMTggTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0IEFcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBpXHViYzg4XHVjOWY4IFx1YzIxOFx1YWMwMCBcdWFkZjggXHVjNTVlXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMTggXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjMjE4XHViOTdjIFx1Yzg4Ylx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIChcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWI5N2MgXHVjNWVjXHViN2VjXHViYzg4IFx1YjM1NFx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkMWQgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjODhiXHVjNzQwIFx1YzIxOCBcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjQgQVx1Yzc1OCBcdWFjMDEgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwMCwwMDAgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4OGJcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTYyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRPQlJJIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIGEgc2VxdWVuY2UgQSBjb25zaXN0aW5nIG9mIE4gaW50ZWdlcnMgKG5vdCB0byBiZSBjb25mdXNlZCB3aXRoIHRoZSBzZXF1ZW5jZSBmcm9tIHRoZSBwcmV2aW91cyB0YXNrKS4gV2Ugd2lsbCBjYWxsIHRoZSBpPHN1cD50aDxcL3N1cD4gc2VxdWVuY2UgZWxlbWVudCBnb29kIGlmIGl0IGVxdWFscyB0aGUgc3VtIG9mIHNvbWUgdGhyZWUgZWxlbWVudHMgaW4gcG9zaXRpb25zIHN0cmljdGx5IHNtYWxsZXIgdGhhbiBpIChhbiBlbGVtZW50IGNhbiBiZSB1c2VkIG1vcmUgdGhhbiBvbmNlIGluIHRoZSBzdW0pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ib3cgbWFueSBnb29kIGVsZW1lbnRzIGRvZXMgdGhlIHNlcXVlbmNlIGNvbnRhaW4/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDUwMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSBBLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgcmVwcmVzZW50aW5nIHRoZSBzZXF1ZW5jZSBBICgtMTAwIDAwMCAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMTAwIDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbnVtYmVyIG9mIGdvb2QgZWxlbWVudHMgaW4gdGhlIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=