NOTATRI  Not a Triangle
You have N (3 ≤ N ≤ 2,000) wooden sticks, which are labeled from 1 to N. The ith stick has a length of L_{i} (1 ≤ L_{i} ≤ 1,000,000). Your friend has challenged you to a simple game: you will pick three sticks at random, and if your friend can form a triangle with them (degenerate triangles included), he wins; otherwise, you win. You are not sure if your friend is trying to trick you, so you would like to determine your chances of winning by computing the number of ways you could choose three sticks (regardless of order) such that it is impossible to form a triangle with them.
Input
The input file consists of multiple test cases. Each test case starts with the single integer N, followed by a line with the integers L_{1}, ..., L_{N}. The input is terminated with N = 0, which should not be processed.
Output
For each test case, output a single line containing the number of triples.
Example
Input: 3 4 2 10 3 1 2 3 4 5 2 9 6 0 Output: 1 0 2
For the first test case, 4 + 2 < 10, so you will win with the one available triple. For the second case, 1 + 2 is equal to 3; since degenerate triangles are allowed, the answer is 0.
hide comments
sahil786k:
20210216 14:34:33
is there any better approach to solve it in less than n*n*logn complexity 

saurabh_kl:
20210213 17:05:56
Code accepting in java with O(n*n*logn) time complexity but I not used Scanner class for input 

shivamyadav00:
20201012 08:55:55
Python solution gets TLE, the same solution on Codechef got AC.


wille_25:
20200731 08:17:12
finally AC in 0.13 s ..simply sorted & used upper bound ...NOTE:: put endl after the answer !!. 

noobmaster__69:
20200719 19:15:47
If the sum of two sides is equal to the third side then also it doesn't form a triangle. But in this question it assumes the contrary. 

raman_111:
20200528 08:37:15
think practically,


robosapien:
20200527 01:52:56
o(n*n*logn) works within tl 

manish_thakur:
20200424 08:15:04
sorting and lower bound


sayan_244:
20200129 18:09:36
distinct indexes matter not the the lengths.


ntnguyen:
20200129 07:06:11
Note: Do "not" print a new line after the output ends.

Added by:  Neal Wu 
Date:  20080803 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 