Farmer John 的奶牛联盟（UCFJ）将派遣代表团参加 International bOvine olympIad（IOI）。

共有 $N$ 头奶牛参与代表团选拔（$1 \leq N \leq 2 \cdot 10^5$）。她们排成一列，奶牛 $i$ 的品种为 $b_i$。

代表团由至少两头奶牛组成的连续区间构成，即满足 $1\le l<r\le N$ 的整数 $l$ 和 $r$ 所确定的奶牛 $l\ldots r$。选定区间两端的奶牛被指定为“领队”。为了避免同品种内部的冲突，每头领队的品种必须不同于代表团中其余所有奶牛的品种（无论是否为领队）。

请帮助 UCFJ 出于税务原因确定选出一个代表团参加 IOI 的方案数。

输入格式

第一行包含 $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

13

说明

每个代表团对应以下领队对之一：

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

子任务

• 测试用例 1–3 满足 $N\le 100$。
• 测试用例 4–8 满足 $N\le 5000$。
• 测试用例 9–20 没有额外限制。

题目署名：Benjamin Qi