Count unordered index pairs (i, j) such that i < j and aᵢ = aⱼ.

What counts as a pair? A pair is determined by two different positions, not by two adjacent elements. For example, if a value occurs at positions 2, 4, and 5, it creates the three pairs (2, 4), (2, 5), and (4, 5). In general, a value occurring f times contributes f × (f − 1) / 2 pairs.

Input

The first line contains n (1 ≤ n ≤ 100000). The second line contains n integers |aᵢ| ≤ 10^9.

Output

Print the number of equal pairs.

Examples

Input #1

6
5 3 1 2 1 1

Output #1

3

Input #2

5
4 1 1 2 2

Output #2

2