Batyr 最近过生日，Tima 送了他一份独特的礼物——一个包含 $N$ 个整数的序列 $A$。Batyr 非常喜欢这份礼物，并立即开始分析该序列的性质。他最感兴趣的是“优美三元组”（beuatiful triplets）：满足 $1 \le i \le j < k \le n$ 的三元组 $(i, j, k)$，使得序列中从 $i$ 到 $j$（包含两端）这一段中出现的所有数字，在从 $j + 1$ 到 $k$ 这一段中也全部出现，反之亦然（详见“说明”部分）。

Batyr 一直在仔细地统计这类三元组的数量，但讨厌的 Donchik 删除了他所有的记录。请帮助 Batyr——根据他的序列统计“优美三元组”的数量。

输入格式

第一行包含一个整数 $N$——Batyr 序列的长度。下一行包含 $N$ 个整数，第 $i$ 个整数描述序列的第 $i$ 个元素 $a_i$ ($1 \le a_i \le N$)。

输出格式

输出一个整数——“优美三元组”的数量。

子任务

本题共有 7 个子任务，满足以下限制：

1. $N \le 100$。分值 5 分。
2. $N \le 500$。分值 7 分。
3. $N \le 5000$。分值 12 分。
4. $N \le 2 \times 10^5$，$1 \le a_i \le 2$，对于每个 $1 \le i \le N$。分值 12 分。
5. $N \le 2 \times 10^5$，$1 \le a_i \le 50$，对于每个 $1 \le i \le N$。分值 12 分。
6. $N \le 2 \times 10^5$，$A$ 中的每个数字恰好出现两次。分值 12 分。
7. $N \le 2 \times 10^5$。分值 40 分。

样例

样例输入 1

5
1 2 2 2 1

样例输出 1

6

样例输入 2

10
1 2 1 1 2 1 2 2 2 1

样例输出 2

66

说明

第一个样例的答案包含以下三元组：

1. $(1, 2, 5)$
2. $(1, 3, 5)$
3. $(2, 2, 3)$
4. $(2, 2, 4)$
5. $(2, 3, 4)$
6. $(3, 3, 4)$