通过了第一关的你，被引入古老的魔法遗迹。

这里整齐排列着 $n$ 块刻有神秘印记的符文石，每块符文石的印记用一个整数编号表示，代表它所属的魔法流派。

传说，只有 成对 唤醒并消除 同一流派 的符文石，才能释放出强大的能量。于是，你需要主持一场符文消除仪式：

• 每次选择 两块同一流派的符文石，将它们同时移出阵列；
• 移除时，将它们在当前阵列中的位置差加入总能量；
• 移除后，遗迹中的剩余符文石的位置重新编号为 $1,2,3,\dots$；
• 仪式不断重复，直到遗迹中不再有同一流派的符文石能成对消除为止。

你的目标是通过合理安排消除顺序，使最终释放的总能量最大化。

输入格式

第一行一个整数 $n$，符文石数量。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示阵列中从左到右第 $i$ 块符文石的魔法流派编号。

输出格式

输出一个整数，表示最大可能释放的总能量。

样例

样例 1 输入

6
1 2 1 2 1 2

样例 1 输出

7

样例 1 解释

符文石初始序列为：$[1,2,1,2,1,2]$。

步骤 $1$：选择位置 $1$ 和 $5$（流派 $1$），消除它们。

位置差 $=5-1=4$，累积能量 $=4$。

剩余符文（重新编号）：位置 $2,3,4,6 \to$ 符文 $[2,1,2,2]$。

步骤 $2$：选择位置 $1$ 和 $4$（流派 $2$），消除它们。

位置差 $=4-1=3$，累积能量 $=4+3=7$。

剩余符文（重新编号）：位置 $2,3 \to$ 符文 $[1,2]$。

步骤 $3$：无法再找到同流派符文石，仪式结束。

总能量：$7$。

样例 2 输入

10
1 2 3 1 1 2 2 2 2 3

样例 2 输出

17

数据范围

对于所有测试点，满足 $1\le n\le 5\times 10^{5}$，$1\le a_i\le n$。

子任务