#D. 序列归位-hard

传统题

2000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$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