Zoo

Interview

Time limit2sMemory limit1024 MB

Summary

Count the ways to pick three animals of pairwise different species, given the population of each species.

Level: Medium4 of 10
Topics: Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

A city zoo keeps animals of $n$ different species. To take part in the international exhibition "Three Beasts", the zoo must present three animals of different species. The zookeepers now want to know in how many ways three animals can be chosen for the exhibition.

For example, if the zoo has two bears, a tiger, a lion, and a penguin, there are seven ways to choose three animals:

the first bear, the tiger, and the lion;
the first bear, the tiger, and the penguin;
the first bear, the lion, and the penguin;
the second bear, the tiger, and the lion;
the second bear, the tiger, and the penguin;
the second bear, the lion, and the penguin;
the tiger, the lion, and the penguin.

Input

The first line of the input file contains a positive integer $n$ , the number of animal species in the city zoo ( $1 \le n \le 10^5$ ).

Each of the next $n$ lines contains one positive integer, the number of animals of the corresponding species. The total number of animals in the zoo does not exceed $10^5$ .

Output

Output the number of ways to choose three animals for the international exhibition.

Examples2

Example 1
Input
```
4
2
1
1
1
```
Expected output
```
7
```
Example 2
Input
```
3
30000
30000
30000
```
Expected output
```
27000000000000
```