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
y17prashant:
20190322 03:15:55
SImple implementation can be done no need of bin search 

ankur1999:
20190202 14:48:32
Use upper_bound(Time: 0.14s) instead of binary search(Time: 0.18s),


sajalagrawal14:
20190129 15:26:11
AC in one go!!!!!! n2logn complexicity 

anshuman16423:
20181203 15:22:41
Poor support for Python TLE with correct logic


masterchef2209:
20181025 16:51:51
AC in 1 go


salman3007:
20181005 04:07:16
consider each pair and apply binary search for the third 

eagleshadow:
20181002 12:27:36
AC in one go


kumarmapanip1:
20180807 14:28:09
do we need to input the number of test cases??


alankrit_2107:
20180731 18:52:20
Time 0.03s Did it in O(n^2) much better than Binary search. 

the_ashutosh:
20180703 12:48:47
simple use vector and lower bound 
Added by:  Neal Wu 
Date:  20080803 
Time limit:  0.418s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 