A ship’s navigator has dropped their brass astrolabe, shattering its triangular framing. To repair it, they need to forge a new perfect right-angled triangle out of scrap brass rods found in the ship's hold.
The navigator finds a pile of N straight brass rods of various lengths. They want to know how many different ways they can select exactly three rods from the pile to weld together into a valid right-angled triangle.
Because each rod is unique (even if they have the same length), choosing the 1st, 2nd, and 4th rod is considered a different combination than choosing the 1st, 3rd, and 4th rod.
Input
The first line contains a single integer N (3 \le N \le 5000), representing the total number of brass rods in the pile.
The second line contains N space-separated integers (1 \le \text{length} \le 10,000), representing the lengths of the brass rods.
Output
Print a single integer representing the total number of valid right-angled triangles that can be formed by choosing exactly three rods.
Examples
| standard input | standard output |
|---|
| 5
3 1 4 6 5
| 1
|
| 6
5 5 3 4 12 13
| 4
|
Note
Explanation for the first example:
The only rods that can form a right-angled triangle are those with lengths 3, 4, and 5.
Explanation for the second example:
Let the rods be at indices 1 through 6. The valid combinations of indices are:
1. (1, 3, 4) forming a 5-3-4 triangle.
2. (2, 3, 4) forming a 5-3-4 triangle.
3. (1, 5, 6) forming a 5-12-13 triangle.
3. (2, 5, 6) forming a 5-12-13 triangle.