Parmida是一个聪明的女孩,她想参加今年的奥运会。当然,她希望她的伴侣也聪明(尽管他不是)! Parmida 为 Pashmak 准备了以下测试问题。
存在一个序列 a,由 n 个整数 a1, a2, ..., an 组成。我们将 f(l, r, x) 表示为满足以下条件的索引 k 的数量:l ≤ k ≤ r 且 ak = x。他的任务是计算满足 f(1, i, ai) > f(j, n, aj) 的索引对 i, j (1 ≤ i < j ≤ n) 的数量。
帮助 Pashmak 进行测试。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 106)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。
输出
打印一个整数——问题的答案。
示例
输入 #1
7 1 2 1 1 2 2 1
输出 #1
8
输入 #2
3 1 1 1
输出 #2
1
输入 #3
5 1 2 3 4 5
输出 #3
0