Background

Special for beginners, ^_^

Description

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

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

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

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

Format

Input

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

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

Output

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

Samples

6 
1 1 2 3 2 1

14

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

52

Limitation

提示︰本题输入规模较大，请避免使用过慢的输入方式。

对于 40% 的数据：n ≤ 1000，1 ≤ ai ≤ 10，且保证数据随机；

对于 70% 的数据：n ≤ 10^6，1 ≤ ai ≤ 10，且保证数据随机；

对于 90% 的数据：n ≤ 10^6，1 ≤ ai ≤ 10；

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

随机数据的生成方式如下：对于每一个 ai，等概率地从 1 到 10 中产生。