Count Possible Triangles

You have a bag of sticks, and sticks[i] is the length of stick i. Three sticks make a triangle when each one is shorter than the other two put together. Write count_triangles(sticks) that returns how many different groups of three sticks can make a triangle. Sticks with the same length are still different sticks, so groups are counted by position.

Examples

count_triangles([2, 3, 4, 5])   # returns 3
count_triangles([1, 1, 2])      # returns 0
count_triangles([4, 4, 4, 4])   # returns 4

From [2, 3, 4, 5], the groups (2, 3, 4), (2, 4, 5) and (3, 4, 5) work, but (2, 3, 5) does not, because 2 + 3 is not more than 5. With four sticks of length 4, any three of them work, and there are 4 ways to pick three.

Constraints

• 0 <= len(sticks) <= 1,000
• 0 <= sticks[i] <= 1,000

Note

1,000 sticks make about 166 million groups of three. Aim for a number of steps that grows like the square of the length.