题目描述

Shima 开了一座美术馆！他对自己的美术馆非常自豪。其中最著名的展品是纳米团展览：$n$ 个颜色各异的纳米团排成一列。它们排列得非常整齐——任意两个相邻纳米团之间的距离恰好是 $10^9$ 纳米，也就是 $1$ 米。

一天，博物馆评论家 Jerry 前来评价 Shima 的纳米团展览。他的评价过程有些特别。首先，他为展览拍摄若干张照片，而且拍照方式严格满足以下条件：

• 如果两个纳米团出现在同一张照片里，那么它们之间的所有纳米团也都出现在这张照片里；
• 任意两张照片包含的纳米团集合都不完全相同；
• 在不违反前两条条件的前提下，Jerry 已经不可能再为展览多拍一张照片。

拍完全部照片后，Jerry 会为每张照片评分。如果照片中的所有纳米团颜色互不相同，该照片得 $0$ 分；否则，Jerry 找出照片中所有由两个同色纳米团组成的数对，再从中选择距离最近的一对，并把这两个纳米团之间相隔的米数作为照片得分。

Jerry 没时间逐张手工计算，于是把任务交给了乐于助人的助手——你。请计算 Jerry 所有照片的得分之和。

输入格式

第一行包含一个整数 $n$（$1\le n\le4\cdot10^5$），表示纳米团数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（对所有 $i$ 均有 $1\le a_i\le n$），按从左到右的顺序表示各纳米团的颜色。

输出格式

输出一个整数，表示 Jerry 所有照片的得分之和。

5
1 3 2 1 2

9

10
1 4 2 3 5 6 7 10 9 8

0