시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 128 MB 56 23 20 55.556%

문제

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.

Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 (Ai)는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.

문제 요약: N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.

입력

입력은 표준 입력으로 주어진다.

첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.

(1 ≤ N ≤ 10000, -10000 ≤ Ai ≤ 10000)

출력

표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.

예제 입력 1

10 
2 -5 2 3 -4 7 -4 0 1 -6

예제 출력 1

6

힌트

예시에서 가능한 참가자 그룹은 아래와 같다.

(2, -5, 3), (2, 2, -4), (2, 2, -4), (-5, 2, 3), (3, -4, 1), (3, -4, 1)

두 개의 -4는 서로 다른 참가자를 나타내는 것에 유의하라. [ (2,2,-4)와 (3,-4,1)이 두 번씩 나타남 ]

W3sicHJvYmxlbV9pZCI6IjMxNTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NjlcdWM3NzQgMCIsImRlc2NyaXB0aW9uIjoiPHA+RWxseVx1YjI5NCBcdWM2MDhcdWMwYzFcdWNlNTggXHViYWJiXHVkNTU4XHVhYzhjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVjOTAwXHViZTQ0XHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0NCBcdWFjMDBcdWI5NzRcdWNlNjAgXHVjNzA0XHVhZTMwXHVjNWQwIFx1Y2M5OFx1ZDU4OFx1YjJlNC4gXHViMzAwXHVkNjhjXHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDc4OCAzXHViYTg1XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWQzMDBcdWI5Y2MgXHVjYzM4XHVhYzAwXHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1YWRmOFx1YjE0MFx1YWMwMCBcdWFjMDBcdWI5NzRcdWNlNjAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNWQwXHVhYzhjXHViMjk0IFx1ZDA3MCBcdWJiMzhcdWM4MWNcdWFjMDAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWNmNTRcdWI1MjkgXHVjMmU0XHViODI1XHVjNzc0IFx1Yzg4Ylx1YzczY1x1YmE3NCZuYnNwO1x1ZDMwMFx1YzZjY1x1ZDA2Y1x1YWMwMCBcdWI1YThcdWM1YjRcdWM5YzBcdWFjZTAsIFx1ZDMwMFx1YzZjY1x1ZDA2Y1x1YWMwMCBcdWM4OGJcdWM3NDRcdWMyMThcdWI4NWQgXHVjZjU0XHViNTI5IFx1YzJlNFx1YjgyNVx1Yzc3NCBcdWI1YThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNkOWNcdWM4MDRcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YjMwMFx1ZDY4Y1x1YjI5NCBcdWNmNTRcdWI1MjkgXHVjMmU0XHViODI1XHVhY2ZjIFx1ZDMwMFx1YzZjY1x1ZDA2YyBcdWJhYThcdWI0NTBcdWFjMDAgXHVjOTExXHVjNjk0XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5FbGx5XHViMjk0IFx1YWRmOFx1YjE0MFx1YWMwMCBcdWFjMDBcdWI5NzRcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjVcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjUgKEE8c3ViPmk8XC9zdWI+KVx1YjI5NCAtMTAwMDBcdWJkODBcdWQxMzAgMTAwMDAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWIxNDBcdWIyOTQgXHVkMzAwXHVjNmNjXHVkMDZjXHVjNjQwIFx1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjVcdWM3NzQmbmJzcDtcdWJhYThcdWI0NTAgXHVjODAxXHVjODA4XHVkNTVjIFx1ZDMwMFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWMxMzggXHVkMzAwXHVjNmQwXHVjNzU4Jm5ic3A7XHVjZjU0XHViNTI5IFx1YzJlNFx1YjgyNVx1Yzc1OCBcdWQ1NjlcdWM3NzQgMFx1Yzc3NCBcdWI0MThcdWIyOTQgXHVkMzAwXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWM4NzBcdWFjNzQgXHVkNTU4XHVjNWQwLCBcdWFkZjhcdWIxNDBcdWFjMDAgXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2Q5Y1x1YzgwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDMwMFx1Yzc0NCBcdWM1YmNcdWI5YzhcdWIwOTggXHViOWNlXHVjNzc0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjIFx1YzY5NFx1YzU3ZDogTlx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjZjU0XHViNTI5IFx1YzJlNFx1YjgyNSZuYnNwO0E8c3ViPmk8XC9zdWI+XHVhYzAwIC0xMDAwMFx1YmQ4MFx1ZDEzMCAxMDAwMFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHVkNTY5XHVjNzc0IDBcdWM3NzQgXHViNDE4XHViMjk0IDNcdWM3NzhcdWM4NzBcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVhZGY4XHViMTQwXHVhYzAwIFx1YWMwMFx1Yjk3NFx1Y2U2MCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjZjU0XHViNTI5IFx1YzJlNFx1YjgyNVx1Yzc3OCBBPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPigxICZsZTsgTiAmbGU7IDEwMDAwLCAtMTAwMDAgJmxlOyBBPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsgMTAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNDVjXHVjOTAwIFx1Y2Q5Y1x1YjgyNVx1YzczY1x1Yjg1YyBcdWFkZjhcdWIxNDBcdWFjMDAgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMzAwXHVjNzU4IFx1YzIxOFx1Yjk3YyZuYnNwO1x1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMmbmJzcDtcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzJkY1x1YzVkMFx1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjYzM4XHVhYzAwXHVjNzkwIFx1YWRmOFx1YjhmOVx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD4oMiwgLTUsIDMpLCAoMiwgMiwgLTQpLCAoMiwgMiwgLTQpLCAoLTUsIDIsIDMpLCAoMywgLTQsIDEpLCAoMywgLTQsIDEpPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCZuYnNwO1x1YWMxY1x1Yzc1OCAtNFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Y2MzOFx1YWMwMFx1Yzc5MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNWQwIFx1YzcyMFx1Yzc1OFx1ZDU1OFx1Yjc3Yy4mbmJzcDtbICgyLDIsLTQpXHVjNjQwICgzLC00LDEpXHVjNzc0IFx1YjQ1MCBcdWJjODhcdWM1MjkgXHViMDk4XHVkMGMwXHViMGE4IF08XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJaZXJvIFN1bSIsImRlc2NyaXB0aW9uIjoiPHA+RWxseSB1bmV4cGVjdGVkbHkgc3RhcnRlZCB0ZWFjaGluZyBhIHByb2dyYW1taW5nIGNvbnRlc3QgcHJlcGFyYXRpb24gY2xhc3MuIFNvbWUgb2YgdGhlIGNvbnRlc3RzIHRoZXJlIGFyZSBBQ00gc3R5bGUsIGkuZS4gdGhlIGNvbnRlc3RhbnRzIG11c3QgZm9ybSB0ZWFtcyBvZiBleGFjdGx5IHRocmVlIHBlcnNvbnMuIEFmdGVyIHNvbWUgdHJhaW5pbmcgaXQgaXMgdGltZSBmb3IgaGVyIHN0dWRlbnRzIHRvIHNoaW5lICZuZGFzaDsgdGhlIG5hdGlvbmFsIHN0dWRlbnQgT2x5bXBpYWQgaGFzIGNvbWUuIEVsbHkgbXVzdCBkZWNpZGUgd2hpY2ggdGhyZWUgc3R1ZGVudHMgd2lsbCByZXByZXNlbnQgaGVyIGNsYXNzIGluIHRoZSBjb250ZXN0LiBVbmZvcnR1bmF0ZWx5LCBoZXIgc3R1ZGVudHMgaGF2ZSB0aGUgZm9sbG93aW5nIHByb3BlcnR5OiB0aGUgYmV0dGVyIGF0IGNvZGluZyB0aGV5IGFyZSwgdGhlIHdvcnNlIGFyZSB0aGVpciB0ZWFtIHNraWxsczsgb24gdGhlIG90aGVyIGhhbmQsIHRoZSBiZXR0ZXIgdGhlaXIgdGVhbSBza2lsbHMgYXJlLCB0aGUgd29yc2UgdGhleSBjb2RlLiBBbmQgQUNNIGlzIGEgdHlwZSBvZiBjb250ZXN0LCB3aGVyZSBib3RoIGdvb2QgY29kaW5nIGFuZCB0ZWFtIHNraWxscyBhcmUgbmVlZGVkLjxcL3A+XHJcblxyXG48cD5BZnRlciB0aGUgdHJhaW5pbmcgYW5kIHNvbWUgbG9jYWwgY29udGVzdHMsIEVsbHkgaGFzIGEgbGlzdCBvZiB0aGUgY29kaW5nIHNraWxscyBvZiBhbGwgaGVyIHN0dWRlbnRzLiBFYWNoIG9mIHRoZSBOIGNvbnRlc3RhbnRzIGhhcyBhIG51bWJlciBiZXR3ZWVuIC0xMDAwMCBhbmQgMTAwMDAsIGRlbm90aW5nIGhpcyBvciBoZXIgc2tpbGwuIFNoZSB3YW50cyB0byBmb3JtIHRoZSB0ZWFtIGluIHN1Y2ggYSB3YXksIHRoYXQgdGhlIHN1bSBvZiB0aGUgdGhyZWUgY29udGVzdGFudHMgaXMgemVyby4gVGhpcyB3b3VsZCBtZWFuIHRoYXQgdGhlIHRlYW0gaXMgcmVsYXRpdmVseSBiYWxhbmNlZCBib3RoIGZvciBjb2RpbmcgYW5kIHRlYW0gc2tpbGxzLiBHaXZlbiB0aGUgcmVzdWx0cyBvZiB0aGUgc3R1ZGVudHMsIGZpbmQgaW4gaG93IG1hbnkgd2F5cyBzaGUgY2FuIGNob29zZSB0aGUgdGVhbSBmb3IgdGhlIGNvbnRlc3QuPFwvcD5cclxuXHJcbjxwPldlIGNhbiBzdW1tYXJpemUgdGhlIHByb2JsZW0gaW4gdGhlIGZvbGxvd2luZyB3YXk6IEZvciBnaXZlbiBOIGludGVnZXJzIGJldHdlZW4gLTEwMDAwIGFuZCAxMDAwMCB3cml0ZSBhIHByb2dyYW0gemVyb3N1bSwgd2hpY2ggZmluZHMgaG93IG1hbnkgKHVub3JkZXJlZCkgdHJpcGxlcyB3aXRoIHplcm8gc3VtIHRoZXJlIGFyZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGUgaW50ZWdlciBOICZuZGFzaDsgdGhlIG51bWJlciBvZiBzdHVkZW50cyB3aWxsIGJlIGdpdmVuLiBPbiB0aGUgc2Vjb25kIGxpbmUgTiBpbnRlZ2VycyBiZXR3ZWVuIC0xMDAwMCBhbmQgMTAwMDAgJm5kYXNoOyB0aGUgY29kaW5nIHNraWxsIG9mIGVhY2ggc3R1ZGVudCB3aWxsIGJlIGdpdmVuLiZuYnNwOygxICZsZTsgTiAmbGU7IDEwMDAwLCAtMTAwMDAgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBzdGFuZGFyZCBvdXRwdXQgcHJpbnQgYSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBudW1iZXIgb2YgcG9zc2libGUgdGVhbXMgc2hlIGNhbiBjaG9vc2UgZnJvbS48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIHBvc3NpYmxlIHRyaXBsZXMgYXJlOiAoMiwgLTUsIDMpLCAoMiwgMiwgLTQpLCAoMiwgMiwgLTQpLCAoLTUsIDIsIDMpLCAoMywgLTQsIDEpLCAoMywgLTQsIDEpLiBOb3RlIHRoYXQgdGhlIHR3byAtNCBudW1iZXJzIGRlbm90ZSBkaWZmZXJlbnQgY29udGVzdGFudHMuIFRodXMsIHRoZSByZXBlYXRlZCB0cmlwbGUgKDIsIDIsIC00KSBnaXZlcyB0d28gZGlmZmVyZW50IHRlYW1zLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d