Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#0000C7

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.



InputThe standard input contains a line with the single integer N, followed by a line with N integers: L1 , ..., LN .


OutputWrite a single integer representing the number of triples to the standard output.



Input:
3
4 2 10
Output:
1




Input:
3
1 2 3
Output:
0




Input:
4
5 2 9 6
Output:
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.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.