Solved Problem - PnC

In this lesson, we'll discuss a solved PnC Problem.

Problem statement

There are NN different types of balls. There are k1k_1 balls of type 1, k2k_2 balls of type 22, and so on to knk_n. How many ways can you choose 22 balls that are of different types?

Input format

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

The second line contains a sequence k1,k2,...,kNk_1, k_2, ..., k_N where (1ki105)(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 (k1+k2+...+knk_1 + k_2 + ... + k_n) balls

A=(k1+k2+...+kn2)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=(k12)+(k22)+...+(kn2)B= {k_1 \choose 2} + {k_2 \choose 2} + ... + {k_n \choose 2}

The answer is just ABA-B

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

Get hands-on with 1200+ tech skills courses.