Triangular Collection

Interview

Time limit1sMemory limit512 MB

Summary

Count subsets of at least three distinct positive integers in which every triple forms a valid triangle, given n up to 50.

Level: Medium5 of 10
Topics: Sorting, Two pointers, Combinatorics, Greedy
Solved: No attempts yet

Problem

A set of positive integers is called triangular if it has size at least three and, for every triple of distinct integers from the set, a triangle with those three integers as side lengths can be constructed.

Given a set of positive integers, compute the number of its triangular subsets.

Input

The first line contains a single integer $n$ ( $1 \le n \le 50$ ), which is the number of integers in the set.

Each of the next $n$ lines contains a single integer $x$ ( $1 \le x \le 10^9$ ). These are the elements of the set. They are guaranteed to be distinct.

Output

Output a single integer, which is the number of triangular subsets of the given set.

Examples2

Example 1
Input
```
5
3
1
5
9
10
```
Expected output
```
2
```
Example 2
Input
```
10
27
26
17
10
2
14
1
12
23
39
```
Expected output
```
58
```