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

题目描述

小 W 有一个长度为 $n$ 的正整数数组 $A$，从左至右的第 $i$ 个数为 $A_i$。

$A_i$ 将被染成红色或蓝色中的一种，不同的染色方案可能会导致不同的最终得分。设 $\{C_1,C_2,\cdots,C_n\}$ 为分数数组：

• 如果 $A_i$ 左侧没有与其同色的数，则 $C_i = 0$。
• 否则，记其左侧与其最靠近的同色数为 $A_j$，则 $C_i = A_i - A_j$。

小 W 的染色得分为 $C_1+C_2+\cdots +C_n$，请你求出染色得分的最大值。

输入格式

输入共两行。

第一行包含一个正整数 $n$，表示数组长度。

第二行包含 $n$ 个正整数 $A_1, A_2, \dots, A_n$。

输出格式

输出一行包含一个整数，表示染色得分的最大值。

3
1 2 1

1

6
3 4 9 8 2 4

7

提示

【样例 1 解释】

一个最优的染色方案为 $\color{blue}{1\:2} \:\color{red}{1}$，此时最终得分为 $1$。可以证明没有更优的染色方案。

【样例 2 解释】

一个最优的染色方案为 $\color{blue}{3\:4\:9\:8} \:\color{red}{2\:4}$，此时最终得分为 $7$。可以证明没有更优的染色方案。

【样例 3】

见选手目录下的 color/color3.in 与 color/color3.ans。

该样例满足测试点 $16 \sim 20$ 的限制。

【样例 4】

见选手目录下的 color/color4.in 与 color/color4.ans。

该样例满足测试点 $21 \sim 25$ 的限制。

【数据范围】

对于所有测试点，保证：

• $2\le n\le 2\times 10^5$
• $1\le A_i \le 3\times 10^8$

特殊性质：对于所有 $1\le i \le n$，满足 $\dfrac{A_i}{i}$ 为定值。