NOTATRI - Not a Triangle


You have N (3 ≤ N ≤ 2,000) wooden sticks, which are labeled from 1 to N. The i-th stick has a length of Li (1 ≤ Li ≤ 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 L1, ..., LN. 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
karthik1997: 2016-04-01 08:14:42

AC in one Go ;)
Hint: For O(n*n) , Think of window Sliding approach after sorting the array and use int . WIll get easily passed in 0.02 s . P.s : Observing the time of exec , <0.02 is slightly hard but not impossible i guess

Last edit: 2016-04-01 08:15:29
anuj0503: 2016-01-13 18:17:27

Sample case:
10
1 2 3 4 5 6 7 8 9 10
ouput
50

dwij28: 2016-01-05 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: 2015-12-20 01:08:49

AC @one go!! use O(n^2 * log n)...

gulshan_raj: 2015-11-13 11:02:56

Try O(n^2) after doing the obvious O(n^2 log n)

Md. Kishor Morol: 2015-09-05 23:36:36

Can someone please give me some critical test cases? i got WA :(

dev: 2015-08-27 08:31:24

good prob! .after too many tle finally Ac.worth trying :)

SangKuan: 2015-07-05 03:02:54

for first the worst time is log(n - 1) + long(n - 2) + long(n - 3) .. 1
for second is log(n - 2) + log(n -3) ... 1
the last is n - 2
so the total worst time less than (n - 2)^2log(n - 1)

:.Mohib.:: 2015-06-10 21:12:11

Good problem @ps...keep sharing problems like this.. :)

[Mayank Pratap]: 2015-06-08 05:18:02

Good problem for beginners like me!!! Try AGGRCOW after this.. ...


Added by:Neal Wu
Date:2008-08-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO