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
shriyam_011:
20160510 12:28:53
My O(logn*n^2) solution is getting tle!!!!


karthik1997:
20160401 08:14:42
AC in one Go ;)


anuj0503:
20160113 18:17:27
Sample case:


dwij28:
20160105 19:07:14
Got AC with quicksort and binary search, by using int, long long int results in TLE. Any hint on how O(n^2) is possible ? 

iam_ss:
20151220 01:08:49
AC @one go!! use O(n^2 * log n)...


gulshan_raj:
20151113 11:02:56
Try O(n^2) after doing the obvious O(n^2 log n) 

Md. Kishor Morol:
20150905 23:36:36
Can someone please give me some critical test cases? i got WA :( 

dev:
20150827 08:31:24
good prob! .after too many tle finally Ac.worth trying :) 

SangKuan:
20150705 03:02:54
for first the worst time is log(n  1) + long(n  2) + long(n  3) .. 1


:.Mohib.::
20150610 21:12:11
Good problem @ps...keep sharing problems like this.. :) 
Added by:  Neal Wu 
Date:  20080803 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 