Riolku's Mock CCC S2 - Keen Keener Sequence

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Authors:
Problem types

Keen Keen Guglor the Keener is keen to know more about a sequence of N numbers he received yesterday, labeled a_1, a_2, \ldots, 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, \ldots, 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

Comments

There are no comments at the moment.