Trapezoid Map and Trapezoids
Time limit2sMemory limit256 MB
Count sets of four segments that can form a non-degenerate isosceles trapezoid, where the parallel bases and equal legs come from the chosen lengths.
- Level
Medium6 of 10
- Topics
- Combinatorics, Math, Hash map, Sorting
- Solved
- No attempts yet
Problem
One day Anton Sergeyevich was explaining to his students the algorithm for building trapezoid maps. As a warm-up he gave them a problem about trapezoids. He drew n segments on the board. The length of the i-th segment is ai. The students have to find the number of distinct sets of four segments from which an isosceles trapezoid of nonzero area can be formed.
Recall that an isosceles trapezoid is a quadrilateral with two opposite sides parallel and the other two sides equal. An example of an isosceles trapezoid is shown in the figure.
Two sets are considered different if there is a segment that belongs to the first set and does not belong to the second. The indices of the chosen segments in each set must be pairwise distinct.
Help the students find the number of such sets.
Input
The first line contains the number t, the number of times Anton gave this problem to his students. The next 2t lines contain the descriptions of all the problems.
Each problem description consists of two lines. The first line of the description contains the number n, the number of segments drawn on the board. The second line of the description contains n integers ai, their lengths (4 ≤ n ≤ 5000, 1 ≤ ai ≤ 108 for all i from 1 to n).
The total number of segments in all problems does not exceed 5000.
Output
For each problem, output on a separate line a single number: the number of sets sought.