题目描述

贺云艾 获得了一个数列$a_i$，他定义骡马区间（既不神圣也不罗马更非区间）$[l,r]$为满足以下条件的区间：

1.$a_l=a_r,l < r$

2.$\forall i$满足$l < i < r$，有$a_i \neq a_l$

我们定义一个区间$[l,r]$的奥斯曼和为$\sum\limits_{i=l}^r a_i$，贺云艾 想让你求出所有骡马区间的奥斯曼和的和。

输入格式

第一行一个整数$n$，为数列的长度。

接下来一行$n$个整数，为数列的数$a_i$。

输出格式

输出仅一个整数，为答案。

样例

样例输入

4
1 2 1 2

样例输出

9

数据范围与提示

$1 \leq n \leq 10^5$

$1 \leq a_i \leq 10^8$