题目描述

小红有一个长度为 n 的数组a，记 f(l, r, x) 为区间 [l, r] 内 x 的出现次数。

现在小红想知道有多少对 i < j 满足 f(0, i, $a_i$) > f(j, n-1, $a_j$)。

输入描述

第一行一个整数 n。第二行 n 个整数 $a_0$, $a_2$, ..., $a_n-1$。

$1 \leq n \leq 10^5$

$1 \leq a_i \leq 10^9$

输出描述

输出一个整数表示答案。

输入示例

6
1 2 1 2 2 1

输出示例

5

提示信息

存在以下五对 (i, j)满足条件：(2, 4) (2, 5) (3, 4) (3, 5) (4, 5).

时间限制：c/c++：1s；其他语言：4s。