T488688 [CZSC 2024] 填数游戏

# 请反复确认代码问题不大后再提交！或者直到比赛快结束时再提交！

明陌 正在玩一个填数游戏。 他的眼前有 $n$ 个格子，第 $i$ 个格子的编号为 $i$。每个格子都有一个分数，第 $i$ 个格子的分数为 $s_i$。 明陌 需要将数字 $1$ 到 $n$ 这 $n$ 个数填入这些格子中。若填入的数字小于该格子的编号，则 明陌 的分数加上该格子的分数；若填入的数字大于该格子的编号，则 明陌 的分数减去该格子的分；若填入的数字等于该格子的编号，则 明陌 的分数不变。明陌 的初始分数为 $0$。格子的分数可能为负数。 明陌 只有获得所有填入情况中的最高分才可以通关。 由于 明陌 期末考试不及格需要补习，但他仍然急于通关该游戏，所以他请你帮忙通关该游戏。

第一行输入一个正整数 $n$，表示格子的数量。 第二行输入 $n$ 个正整数，第 $i$ 个整数 $s_i$，表示编号为 $i$ 的格子的分数。

输出一行，一个正整数，表示你帮助 明陌 获得的最大分数。

**【样例 1 解释】** 三个格子的所有填数情况如下： * 分别填入 `1 2 3` 时，获得分数为 $0+0+0=0$ * 分别填入 `1 3 2` 时，获得分数为 $0-(-2)+(-3)=-1$ * 分别填入 `2 1 3` 时，获得分数为 $-1+(-2)+0=-3$ * 分别填入 `2 3 1` 时，获得分数为 $-1-(-2)+(-3)=-2$ * 分别填入 `3 1 2` 时，获得分数为 $-1+(-2)+(-3)=-6$ * 分别填入 `3 2 1` 时，获得分数为 $-1+0+(-3)=-4$ 因此答案为 `0` 。 **【样例 2 解释】** 填入 `6 1 2 3 4 5` , 获得分数 $-1+1+4+5+1+4=14$。可以证明这种填数方案是最优方案。 **【样例 3 解释】** 填入 `3 4 5 6 1 2` , 获得分数 $-(-1)-(-9)-(-1)-(-9)+8+10=38$。可以证明这种填数方案是最优方案。 **【样例 4 解释】** 填入 `2 1 6 5 4 3 7 8` , 获得分数 $-1+2-(-3)-(-4)+5+6+0+0=19$。可以证明这种填数方案是最优方案。 **【数据范围】** 对于所有数据，保证 $1\le n \le 10^5$， $-10^5 \le s_i \le 10^5$。 |测试点编号|$n$|特殊性质| |-|-|-| |$1\sim3$|$=4$|无| |$4\sim5$|$\le 8$|无| |$6\sim7$|$\le 10^3$|$AC$| |$8\sim9$|$\le 10^3$|$C$| |$10\sim11$|$\le 10^3$|$B$| |$12\sim13$|$\le 10^3$|无| |$14\sim15$|$\le 10^5$|$AC$| |$16\sim17$|$\le 10^5$|$B$| |$18\sim19$|$\le 10^5$|$C$| |$20\sim 25$|$\le 10^5$|无| 特殊性质 $A$：保证所有格子的分数均相同。 特殊性质 $B$：保证从格子 $1$ 到格子 $n$ 的分数是单调递增的。 特殊性质 $C$：保证所有格子的分数均为正数。