EIU Programming Practices and Exams

Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles. For a triangle to be possible from 3 values, the sum of any two values (or sides) must be greater than the third value (or third side).
For example, if the input array is {4, 6, 3, 7}, the output should be 3. There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle.

Input

The first line is an integer N

The next line contains N integers corresponding to the length of one side of a triangle.

Output

The number of possible triangles

Testcase:

https://drive.google.com/file/d/1ESqzd5Ad7URl_ThfpN3UKMpiCzwN3mEd/view?usp=share_link

Example

Input:
5
1 4 3 6 2

Output:
2