The city zoo contains animals of n different species. To participate in the international exhibition "Three critters" the zoo must present three animals of various species. Now the zoo ministers are interested in how many ways you can choose three animals to participate in the exhibition.

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

1. first bear, tiger and lion;
2. first bear, tiger and penguin;
3. first bear, лев and penguin;
4. second bear, tiger and lion;
5. second bear, tiger and penguin;
6. second bear, lion and penguin;
7. tiger, lion and penguin.

Input

The first line contains the number of animal species n (1 ≤ n ≤ 105) in the city zoo. Each of the following 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 105.

Output

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