CF459D Pashmak and Parmida's problem

Parmida 是一个聪明的女孩，她今年想参加奥林匹克竞赛。当然，她也希望她的搭档同样聪明（尽管他不是）！Parmida 为 Pashmak 准备了如下测试题目。 有一个由 $n$ 个整数 $a$ 组成的序列 $a_{1},a_{2},...,a_{n}$。我们定义 $f(l,r,x)$ 表示在区间 $l \leq k \leq r$ 中有多少个下标 $k$ 满足 $a_{k} = x$。他的任务是计算有多少对下标 $i, j$，满足 $1 \leq i < j \leq n$ 并且 $f(1, i, a_{i}) > f(j, n, a_{j})$。 请帮助 Pashmak 解答这个测试题。

第一行包含一个整数 $n$，$(1 \leq n \leq 10^{6})$。 第二行包含 $n$ 个用空格分隔的整数 $a_{1}, a_{2}, ..., a_{n}$，$(1 \leq a_{i} \leq 10^{9})$。

输出一个整数，表示符合条件的下标对数。

由 ChatGPT 5 翻译