题目描述

dash要练习数组。一次，dash得到了一个长度为 $n$ 的数组 $a$。

现在，对于每一个下标 $i$，dash想找出比 $i$ 小且距离 $i$ 最近 的下标 $j$，使得满足 $a_i \neq a_j$，如果不存在，则 $j = 0$。记下标 $i$ 对应的答案 $f_i = j$，dash为了确保自己的程序正确，想让你来检查 $f$ 数组。

可你不能告诉他整个答案，你只需要告诉他 $f$ 数组所有元素的和即可。

输入格式

共两行，第一行一个正整数 $n$，表示数组长度；

第二行 $n$ 个正整数，第 $i$ 个表示 $a_i$。

输出格式

仅一行一个数，表示 $f$ 数组所有元素的和。

样例

6
1 1 2 3 2 1

14

解释#1

$f_i$ 依次为 $(0, 0, 2, 3, 4, 5)$，总和为 $14$。

12
3 3 3 3 2 2 2 2 4 4 1 1

52

解释#2

$f_i$ 依次为 $(0, 0, 0, 0, 4, 4, 4, 4, 8, 8, 10, 10)$，总和为 $52$。

数据范围

对于 $100\%$ 的数据：$n ≤ 10^6，1 ≤ a_i ≤ 1000$。