Given an array $A$ of $n$ integers. Count the number of sets $(i, j, k)$ that $i < j < k$ and edges of length $A_i, A_j, A_k$ can form an triangle.
For example, you can't form an triangle out of three edges of length $1, 2, 4$.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integer $A_i$.
### Output
- The number of sets $(i, j, k)$ which can form an triangle.
### Constraints
- $1 \le n \le 1500$.
- $1 \le A_i \le 10^9$.
### Example
Input:
```
4
1 2 3 4
```
Output:
```
1
```
