Problem statement

There are $N$ different types of balls. There are $k_1$ balls of type 1, $k_2$ balls of type $2$, and so on to $k_n$. How many ways can you choose $2$ balls that are of different types?

Input format

The first line contains one positive integer N $(1 \leq N \leq 10^5)$ – the number of types of balls.

The second line contains a sequence $k_1, k_2, ..., k_N$ where $(1 \leq k_i \leq 10^5)$ - the count of balls of each type.

Output format

Print a single integer to answer the problem.

---

Sample

Input 1

3
2 1 1

Output 1

5

Input 2

4
1 2 2 2

Output 2

18

---

Solution

We will subtract the non-desirable number of ways from the totals,

Total number of ways - Pick 2 from ($k_1 + k_2 + ... + k_n$) balls

$A = {k_1 + k_2 + ... + k_n \choose 2}$

Non-desirable case - when both balls are of the same type. The number of ways to pick that is:

$B= {k_1 \choose 2} + {k_2 \choose 2} + ... + {k_n \choose 2}$

The answer is just $A-B$

Note: Use long long int since the result can overflow int.