题目描述

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$。
第二行包含 $n$ 个用空格分隔的整数 $a_{1}, a_{2}, ..., a_{n}$。

输出格式

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

7
1 2 1 1 2 2 1

8

3
1 1 1

1

5
1 2 3 4 5

0

说明 / 提示

由 ChatGPT 5 翻译

数据范围

$(1 \leq n \leq 10^{6})$

$(1 \leq a_{i} \leq 10^{9})$