Sophie 的父母为她最喜欢的动画片制作了一张 DVD。当她想看动画片时，父母会为她播放一个剧集区间，即 DVD 上一段连续的剧集序列。

不幸的是，他们在制作 DVD 时有些粗心：有些剧集重复了，这让 Sophie 很不喜欢。如果一个剧集区间中至少有一个剧集只出现了一次（即该剧集与区间内的其他所有剧集都不同），那么这个区间对 Sophie 来说就是有趣的。此外，Sophie 有时会错过区间开头的几集（因为她想多玩一会儿玩具），有时她不会看完整个区间，从而错过了结尾的几集。因此，如果一个剧集区间的所有子区间都是有趣的，那么这个区间就是非常有趣的。

Sophie 的父母想知道，DVD 上的哪些剧集区间是非常有趣的？请帮助他们——给定 DVD 上的完整剧集序列，计算其中有多少个子区间是非常有趣的？

输入格式

输入的第一行包含一个自然数 $n$（$1 \le n \le 500\,000$），表示 DVD 上的剧集总数。

第二行（也是最后一行）包含 $n$ 个自然数，其中第 $i$ 个数表示第 $i$ 集的编号 $a_i$（$1 \le a_i \le 10^9$）。

输出格式

输出一个自然数：输入中给定的动画片序列中非常有趣的区间数量。

样例

输入 1

5
1 6 1 6 6

输出 1

10

输入 2

6
1 2 3 1 2 3

输出 2

20

说明

在样例 1 中，以下序列是有趣的：所有长度为 1 的序列；三个长度为 2 的序列（只有 $(6, 6)$ 是无趣的）；所有三个长度为 3 的序列；以及一个长度为 4 的序列——$(6, 1, 6, 6)$。在这些序列中，序列 $(1, 6, 6)$ 和 $(6, 1, 6, 6)$ 不是非常有趣的（因为它们包含了无趣的子序列 $(6, 6)$）。

在样例 2 中，只有完整的序列 $(1, 2, 3, 1, 2, 3)$ 不是非常有趣的。