Riolku's Mock CCC S2 - Keen Keener Sequence (Hard version)

View as PDF

Submit solution

Points: 12
Time limit: 2.0s
Memory limit: 512M

Authors:
Problem types

Note: this is a harder version of this problem. The only difference between this problem and that one are the constraints.

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 7 \times 10^3

1 \le a_i \le 10^9

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 (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