Условие недоступно на русском языке
I. 2-冲突数对
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一个大小为 n 的数组 [a1, a2, ..., an] 。

定义满足以下条件的有序下标对 (i, j) 称为 "2- 冲突数对" ：

  • 1 ≤ i < j ≤ n
  • ai ≠ aj

冲突数对 (i1, j1) 和 (i2, j2) 不同，当且仅当 i1 ≠ i2 或 j1 ≠ j2 。

你需要求出有多少种不同的 "2-冲突数对" 。

Input

第一行一个整数 n（1 ≤ n ≤ 105），表示序列长度。

第二行 n 个整数 a1, a2, ..., an（1 ≤ ai ≤ 105），表示序列中的元素。

Output

输出一行一个整数，表示有多少种不同的 "2-冲突数对" 。

Examples
Input
3
1 1 2
Output
2
Input
5
1 2 3 2 1
Output
8