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
changyouren: 2021-09-22 06:37:08

use two pointers can solve it in O(n * n)

sahil786k: 2021-02-16 14:34:33

is there any better approach to solve it in less than n*n*logn complexity

saurabh_kl: 2021-02-13 17:05:56

Code accepting in java with O(n*n*logn) time complexity but I not used Scanner class for input

shivamyadav00: 2020-10-12 08:55:55

Python solution gets TLE, the same solution on Codechef got AC.

[NG]: It's possible in Python: https://www.spoj.com/ranks/NOTATRI/lang=PYTH%202.7 , submit in PyPy when out of speedup ideas.

Last edit: 2020-10-13 00:38:31
wille_25: 2020-07-31 08:17:12

finally AC in 0.13 s ..simply sorted & used upper bound ...NOTE::- put endl after the answer !!.

noobmaster__69: 2020-07-19 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: 2020-05-28 08:37:15

think practically,
first time I found a classic problem where (n*n*logn) accepted

robosapien: 2020-05-27 01:52:56

o(n*n*logn) works within tl

manish_thakur: 2020-04-24 08:15:04

sorting and lower bound

sayan_244: 2020-01-29 18:09:36

distinct indexes matter not the the lengths.
The problem statement is bit clever.

Would have been better to include a testcase with same lengths


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