← 返回题目列表

Codeforces · 459/D

D. Pashmak 和 Parmida 的问题

中文机器翻译题面 查看原题

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