3SUM est un problème algorithmique bien connu dans lequel, pour une séquence donnée d'entiers $c_1, c_2, \dots, c_m$, il faut trouver trois indices $i < j < k$ tels que $c_i + c_j + c_k = 0$.
Il n'existe pas de solution connue à ce problème pour des séquences d'entiers arbitraires avec une complexité significativement meilleure que $O(m^2)$. Heureusement, Bajtek ne le sait pas et a décidé de résoudre ce problème pour sa "Très Favorite Séquence".
La Séquence Favorite de Bajtek se compose de $n$ entiers $a_1, a_2, \dots, a_n$. La Très Favorite Séquence de Bajtek est formée en examinant tous les $\frac{n(n+1)}{2}$ intervalles contigus de la Séquence Favorite de Bajtek, en calculant la somme des éléments de chacun d'eux, et en plaçant toutes ces sommes dans une seule séquence (en incluant les répétitions). Les sommes des intervalles sont ordonnées par ordre croissant selon l'indice de début de l'intervalle, et en cas d'égalité, par ordre croissant selon l'indice de fin de l'intervalle.
Pour ne pas rendre les choses trop simples, Bajtek ne s'intéresse pas à la recherche d'un triplet d'indices $i < j < k$. Il souhaite connaître le nombre exact de tous les triplets d'indices $i < j < k$ correspondant à des éléments dont la somme est égale à zéro. Aidez-le et écrivez un programme qui calcule pour lui le nombre de tels triplets !
Entrée
La première ligne de l'entrée standard contient un entier $n$ ($1 \le n \le 500$), représentant la longueur de la Séquence Favorite de Bajtek.
La ligne suivante contient $n$ entiers $a_i$ ($|a_i| \le 20\,000$), représentant les éléments successifs de la Séquence Favorite de Bajtek.
Sortie
La première et unique ligne de la sortie standard doit contenir un seul entier – le nombre de triplets d'indices $i < j < k$ correspondant aux termes de la Très Favorite Séquence de Bajtek qui somment à $0$.
Exemples
Entrée 1
3 7 -4 -2
Sortie 1
1
Entrée 2
10 0 0 0 0 0 0 0 0 0 0
Sortie 2
26235
Remarque
Dans le premier exemple, la Très Favorite Séquence est $[7, 3, 1, -4, -6, -2]$, et le seul triplet d'éléments distincts dont la somme est égale à $0$ est $3 + 1 + (-4)$, d'où la réponse $1$.
Dans le deuxième exemple, la Très Favorite Séquence de Bajtek se compose de cinquante-cinq zéros. Pour trois indices quelconques $i < j < k$, la somme des éléments correspondants est égale à $0$, et il existe $26\,235$ tels triplets.