题目描述

小 C 终于成为一名萌新 OIer，最近他在学习数组。

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

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

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

输入格式

从文件 array.in 中读取数据。

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

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

输出格式

输出到文件 array.out 中。

仅一行一个数，表示 $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$。

样例3

见选手目录下的 array/array3.in 和 array/array3.ans。

数据范围

对于 $40\%$ 的数据：$n ≤ 1000，1 ≤ a_i ≤ 10$，且保证数据随机； 对于 $70\%$ 的数据：$n ≤ 10^6，1 ≤ a_i ≤ 10$，且保证数据随机； 对于 $90\%$ 的数据：$n ≤ 10^6，1 ≤ a_i ≤ 10$； 对于 $100\%$ 的数据：$n ≤ 10^6，1 ≤ a_i ≤ 1000$。 随机数据的生成方式如下：对于每一个 $a_i$，等概率地从 $1$ 到 $10$ 中产生。