Farmer John 的联合奶牛组织（UCFJ）正在派遣一个代表团参加国际牛类奥林匹克竞赛（IOI）。
共有 $N$ 头奶牛参与代表团选拔（$1 \leq N \leq 2 \cdot 10^5$）。它们排成一排，第 $i$ 头奶牛的品种为 $b_i$。
代表团将由至少三头奶牛组成的连续区间构成，即满足 $1 \le l < r \le N$ 且 $r-l \ge 2$ 的奶牛区间 $l \ldots r$。在选定的区间中，有三头奶牛被标记为代表团领队。出于法律原因，选定区间的两端奶牛必须是领队。此外，为了避免品种间的冲突，每一位领队的品种必须与代表团中其余所有奶牛（无论是否为领队）的品种都不同。
请帮助 UCFJ 确定（出于税务原因）他们可以选择多少种派遣代表团的方案。如果两个代表团的成员不同，或者领队不同，则视为不同的代表团。
输入格式
第一行包含 $N$。
第二行包含 $N$ 个整数 $b_1, b_2, \ldots, b_N$，每个整数都在 $[1, N]$ 范围内。
输出格式
输出可能的代表团数量，占一行。
注意：本题涉及的整数较大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 long long）。
样例
样例输入 1
7 1 2 3 4 3 2 5
样例输出 1
9
每个代表团对应以下三位领队组合之一：
$$(1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7).$$
子任务
- 测试点 1-2 满足 $N \le 50$。
- 测试点 3-4 满足 $N \le 500$。
- 测试点 5-8 满足 $N \le 5000$。
- 测试点 9-20 无额外限制。
题目来源：Benjamin Qi