After fiddling with numbers for too long, Mr. DeMello has decided to work with spooky arrays! However, he is not very good with them; he has had a question on his mind for a while but cannot solve it, so he asks you for help:

Given an array, find the number of valid solutions for $A_i+A_j+A_k=A_l$, where $(i,j,k,l)$ are strictly increasing $(i<j<k<l)$.

Can you help him?

Constraints

For all subtasks:

$1\le A_i\le 100$

Subtask 1 [10%]

$1\le N\le 100$

Subtask 2 [20%]

$1\le N\le 600$

Subtask 3 [70%]

$1\le N\le 100000$

Input Specification

The first line will contain $N$, the number of array elements.

The second line will contain $N$ space-separated integers, $A_i$, the elements of the array.

Output Specification

Output the number of valid solutions to the given equation $(A_i+A_j+A_k=A_l)$.

Sample Input

8
1 1 2 3 1 1 2 3

Sample Output

4

Explanation for Sample Output

The valid solutions are $(i=1,j=2,k=5,l=8)$, $(i=1,j=2,k=6,l=8)$, $(i=1,j=5,k=6,l=8)$, $(i=2,j=5,k=6,l=8)$.

Note that the indices are 1-indexed.