L最近喜欢上了一个卡片游戏，游戏规则是： 2个人一共拿2n张卡片，编号1…2n，每个人n张，然后进行n轮出牌，每轮2个人都打一张牌，，点数大的玩家每次获1分

L可以预测到对方要打牌的顺序。

同时，L有一次机会选择了某个时间点，从那个时候开始，每回合点数少者获胜。

请你帮助L获得最大的分数

接下来n行表示，对手每次的出牌，根据这些数字，你一定知道了L手上的牌的吧

1个整数，表示L能获得最高分数

这道题真的考场上都没人$$A，（要不是我读优打错我就成为全场唯一$$

这绝对是我做过的最难的贪心的题了。

思路从暴力转到一个不如暴力的二分图匹配，再转到正解是真的爽。

暴力就是枚举断点，田忌赛马式的贪心。田忌赛马的意思就是，我只比你大一点。我们拿$$L能得分的最接近他朋友的牌来得分。最后贪心出来还是错的。。。（为什么，下面二分图匹配里面有讲）。

二分图匹配是优化后的暴力，但是建边是${}^{}$O(n2)的，无法承受。

最后这个令人窒息的正解，比暴力不知道短了多少。

实际上回到最后还是田忌赛马式的贪心。

这样可以保证，枚举任何一个点为断点，我们都能够得到一个合法的方案，也就是说，在前后出的牌没有交集。

那就完了啊，这道题正着最大值做一遍，反着最小值做一遍，最后$$O(n)统计一下就好了啊。

这样求出来的没有交集吗？

由于原来牌中最小的目前仍然在手里，那么在进入第二阶段的时候就会有足够的小牌满足我们的任何贪心策略，同样采用田忌赛马的策略，最后将我们出的牌收回，放出最小的牌。

剩下不能得分的牌随便放就行了。

可以证明这能够令前后阶段的出牌没有交集，因为前阶段得分加后阶段得分不超过n,那么我们只需要在有序数列的两端取最值，显然两个头尾指针是见不了面的。因为最多只有n次取数操作。