Keen Keen Guglor the Keener is keen to know more about a sequence of ~N~ numbers he received yesterday, labeled ~a_1, a_2, \dots, a_N~. More specifically, he wants to compute the number of ordered ~4~-tuples ~(i,j,k,l)~ such that ~i,j,k,l~ are pairwise distinct and ~a_i \times a_j = a_k \times a_l~. Unfortunately, even though he is so keen to know the answer to his question, he was unable to figure it out himself and hopes that you could help him with the problem.

Constraints

~1 \le N \le 1\,500~

~1 \le a_i \le 10^9~

Subtask 1 [1/15]

~1 \le N \le 50~

Subtask 2 [5/15]

~1 \le N \le 400~

Subtask 3 [9/15]

No additional constraints.

Input Specification

The first line will contain the integer ~N~.

The second line will contain the space-separated integers ~a_1, a_2, \dots, a_N~.

Output Specification

On one line, output the number of ~4~-tuples as specified in the problem statement.

Sample Input 1

4
1 2 4 8

Sample Output 1

8

Explanation for Sample Output 1

Our ~8~ tuples are, (with the elements representing the indices), ~(1, 4, 2, 3), (4, 1, 2, 3), (1, 4, 3, 2), (4, 1, 3, 2), (2, 3, 1, 4), (3, 2, 1, 4), (2, 3, 4, 1)~ and ~(3, 2, 4, 1)~.

Sample Input 2

4
5 5 5 5

Sample Output 2

24

Sample Input 3

10
1 4 8 6 2 9 4 2 5 3

Sample Output 3

160