Hexagons

Time limit2sMemory limit128 MB

Summary

Given up to 80 stick lengths, count distinct equiangular hexagons formed by picking six sticks, treating rotations and reflections as the same shape.

Level: Hard8 of 10
Topics: Geometry, Combinatorics, Math, Brute force
Solved: No attempts yet

Problem

You are given N sticks with integer lengths. Some sticks may have the same length. Choose exactly six sticks and connect them in some order to make a hexagon. You may not join several sticks into one side, and you may not cut a stick into a shorter side. All six interior angles of the resulting hexagon must be equal.

Count how many different hexagons can be made from the given sticks. Hexagons that become the same by rotation or reflection are counted as one.

Input

The first line contains the number of sticks N (6 ≤ N ≤ 80). The second line contains N natural numbers separated by spaces, representing the stick lengths. Each length is at least 1 and at most 1,000,000.

Output

Print the number of different hexagons that satisfy the conditions.

Examples2

Example 1
Input
```
15
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
```
Expected output
```
5
```
Example 2
Input
```
7
24 13 12 7 6 5 4
```
Expected output
```
1
```