Triangle edges - MarisaOJ: Marisa Online Judge

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$

Topic

Binary search

Rating

1000

Solution (0)

Solution