Shima 开了一家艺术博物馆！他为自己的艺术博物馆感到非常自豪，其中最著名的是他的纳米团（nanoblob）展览，展出了 $n$ 个排成一排的各种颜色的纳米团。这些纳米团排列得非常整齐——具体来说，任意两个相邻纳米团之间的距离恰好是 $10^9$ 纳米，即 $1$ 米。

一天，博物馆评论家 Jerry 来评估 Shima 的纳米团展览。他的评估过程有点奇特。他首先对纳米团展览拍了若干张照片。他对拍照的要求非常具体，以至于满足以下条件：

• 如果一张照片中包含两个纳米团，那么它们之间的所有纳米团也都在这张照片中。
• 没有两张照片包含完全相同的纳米团集合。
• Jerry 无法在不违反上述两个条件之一的情况下，再拍摄另一张展览的照片。

拍完所有这些照片后，Jerry 现在开始评估每张照片，并给每张照片一个评分。如果一张照片中的所有纳米团颜色都互不相同，则该照片的分数为零。否则，Jerry 会找出所有颜色相同的纳米团对，并找到其中距离最近的一对，这张照片的分数就等于这两个纳米团之间的距离（单位：米）。

Jerry 没有时间手动为每张照片计算分数，因此他将这项任务外包给了你——他得力的助手。请计算 Jerry 所有照片的分数之和！

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 4 \cdot 10^5$）—— 纳米团的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（对于所有 $i$，满足 $1 \le a_i \le n$），表示从左到右每个纳米团的颜色。

输出格式

输出一个整数：Jerry 所有照片的分数之和。

样例

输入样例 1

5
1 3 2 1 2

输出样例 1

9

输入样例 2

10
1 4 2 3 5 6 7 10 9 8

输出样例 2

0