题目描述

古老的魔法遗迹中，从左到右排列着 $n$ 块神秘之石。

第 $i$ 块石头上刻着一个整数 $a_i$，表示这块石头的种类。

现在你要进行一次消除仪式。每次操作时，你可以选择当前序列中两块种类相同的石头，将它们同时消除。

假设这两块石头在当前序列中的位置分别为 $x$ 和 $y$，其中 $x<y$，那么本次操作会获得 $y-x$ 点能量。

消除后，剩余石头会保持原来的相对顺序，并重新从左到右编号为 $1,2,3,\ldots$。

你可以按照任意顺序进行消除，直到当前序列中不存在两块种类相同的石头为止。

请你求出，在最优的消除顺序下，最多可以获得多少能量。

注意：不一定所有石头都会被消除。最终每种石头最多只会剩下一块。

输入格式

第一行一个整数 $n$，表示石头数量。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示从左到右每块石头的种类。

输出格式

输出一个整数，表示最多可以获得的总能量。

样例 #1

样例输入 #1

6
1 2 1 2 1 2

样例输出 #1

7

样例解释 #1

初始序列为：

1 2 1 2 1 2

一种最优操作方式如下：

1. 消除第 $1$ 块和第 $5$ 块石头，它们的种类都是 $1$，获得能量 $5-1=4$。

   剩余序列为：

   2 1 2 2
   

2. 消除当前序列中的第 $1$ 块和第 $4$ 块石头，它们的种类都是 $2$，获得能量 $4-1=3$。

   剩余序列为：

   1 2
   

此时不存在两块种类相同的石头，仪式结束。

总能量为：

可以证明，最大总能量为 $7$。

样例 #2

样例输入 #2

10
1 2 3 1 1 2 2 2 2 3

样例输出 #2

17

数据范围与子任务

对于所有测试点，满足：

答案可能较大，请使用 64 位整数存储。

本题采用子任务评分。