Can any solve this problems with O(n) time ?

Given an integer sequence of N elements a1, a2, ..., aN. Counts how many ways to choose three terms in the sequence so that the

three terms are chosen as the three sides of a triangle.

Data

• The first line consists of only a positive integer N (N ≤ 10^5);

• The next line contains N integers a1, a2, ..., aN (| ai | ≤ 10^9).

Result

• Print out the number of options that satisfy the topic.

For example

Sample Input

9

Sample Output

1 2 2 2 2 10 99 -9 9 4