题目描述

$Moon$ 拿到了一个颜色序列，长度为 $n$，颜色为 $c_i$ ，与 $\text{easy}$ 版不同，现在 $Moon$ 想要知道

$$\sum\limits_{i=1}^n \sum\limits_{j=1}^i [c_i \neq c_j] \cdot (i-j) $$

输入格式

第一行一个正整数 $n$ （$1 \leq n \leq 2 \times 10^5$）。

第二行 $n$ 个正整数表示 $c_i$（$1 \leq c_i \leq n$）。

输出格式

一个整数表示答案。

输入样例

5
1 3 1 2 2

输出样例

17