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?
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 100\,000~
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 the number of valid solutions to the given equation ~(A_i + A_j + A_k = A_l)~.
8 1 1 2 3 1 1 2 3
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.