题目描述

《孙子兵法》被誉为“兵学圣典”和“古代第一兵书”。它在我国古代军事学术和战争实践中，都起过极其重要的指导作用。

面对强大的敌人，wshcl 和 ET-G 准备分别带领一支队伍前去应战。

$n$ 个需要上场的人排成一排，这 $n$ 个人各自的战力值构成 $1 \sim n$ 的排列。每个人按顺序上场，且要么分配到 wshcl 的队伍，要么分配到 ET-G 的队伍。

众所周知，一个队伍的领导者是很重要的，而 wshcl 和 ET-G 的队伍在对抗敌人时分别具有如下效果：

• wshcl 队伍：逐层击破。对于 wshcl 队伍中的所有选手，若当前上场者的战力值大于 wshcl 队伍之前所有上场者的战力值，则可以对敌方造成一点伤害。

• ET-G 队伍：出奇制胜。对于 ET-G 队伍中的所有选手，若当前上场者的战力值小于 ET-G 队伍之前所有上场者的战力值，则可以对敌方造成一点伤害。

注意第一个上场的人一定可以对敌方造成一点伤害。

在研读兵学圣典、古代第一兵书——孙子兵法之后，wshcl 和 ET-G 在战术和战略上的水平得到了显著提升。为了成功击败敌人，请求出所有分配方式中，对敌方造成的伤害点数之和的最大值。

输入格式

从文件 shung.in 中读入数据。

第一行一个正整数 $n$ ，表示需要上场的人数。

第二行 $n$ 个正整数 $p_{1 \sim n}$，表示按顺序上场的人各自的战力值。

输出格式

输出到文件 shung.out 中。

输出一行一个整数，表示对敌方造成的伤害点数之和的最大值。

样例 #1

样例输入 #1

3
1 2 3

样例输出 #1

3

样例 #2

样例输入 #2

5
4 1 2 3 5

样例输出 #2

5

样例解释 #2

将战力值为 $1,2,3,5$ 的人队伍分配给 wshcl 队伍，将战力值为 $4$ 的人分配给 ET-G 队伍，则 wshcl 队伍对敌方造成的伤害点数之和为 $4$，ET-G 队伍对敌方造成的伤害点数之和为 $1$，总伤害点数之和为 $5$。

样例 #3

样例输入 #3

6
4 2 5 1 6 3

样例输出 #3

5

样例解释 #3

将战力值为 $2,5,6,3$ 的人队伍分配给 wshcl 队伍，将战力值为 $4,1$ 的人分配给 ET-G 队伍，则 wshcl 队伍对敌方造成的伤害点数之和为 $3$，ET-G 队伍对敌方造成的伤害点数之和为 $2$，总伤害点数之和为 $5$。

样例 #4

样例输入 #4

10
3 8 10 4 1 2 7 9 5 6

样例输出 #4

6

样例解释 #4

将战力值为 $3,8,4,1,2,9$ 的人队伍分配给 wshcl 队伍，将战力值为 $10,7,5,6$ 的人分配给 ET-G 队伍，则 wshcl 队伍对敌方造成的伤害点数之和为 $3$，ET-G 队伍对敌方造成的伤害点数之和为 $3$，总伤害点数之和为 $6$。

样例 #5

见选手目录下的 shung/shung5.in 与 shung/shung5.ans 。

数据范围

对于所有数据，保证：

• $2 \le n \le 2 \times 10^5$

• $p_{1 \sim n}$ 为 $1 \sim n$ 的一个排列。

每个测试点的具体限制如下表所示：

特殊性质 A：保证排列随机。

特殊性质 B：保证排列的最长下降子序列长度 $\le 2$。