A carpenter has n wooden planks; plank i has a positive integer length. Count the number of ways to choose 3 of the planks (as an unordered selection of 3 distinct planks; two planks with equal length are still distinguishable by which physical plank they are) such that the three chosen lengths can form a non-degenerate triangle — that is, the sum of the two shorter lengths is STRICTLY greater than the longest length.
Input format
Line 1: an integer n.
Line 2: n space-separated positive integers, the plank lengths.
Output format
A single integer: the number of triples of planks that can form a valid triangle.
Constraints
- 3 ≤ n ≤ 1000
- 1 ≤ length ≤ 1000000