High Card Low Card (Platinum)

题目描述

奶牛 Bessie 非常喜欢纸牌游戏，这很令人惊讶，因为她没有能对握的拇指。不幸的是，牛群里的其他奶牛都不是好对手。她们实在太差了，以至于她们的出牌方式总是完全可预测！尽管如此，Bessie 想要想出如何获胜仍然可能有挑战。

Bessie 和她的朋友 Elsie 正在玩一个简单的纸牌游戏：她们取一副 $2N$ 张牌，方便起见编号为 $1 \ldots 2N$，并将其分成两份，Bessie 拿 $N$ 张，Elsie 拿 $N$ 张。随后两人进行 $N$ 轮游戏，每一轮 Bessie 和 Elsie 都各出一张牌。

起初，出牌点数更高的玩家获得 1 分。然而，在游戏进行到某个时刻，Bessie 可以决定切换规则，使得在接下来的剩余游戏中，出牌点数更低的玩家获得 1 分。Bessie 可以选择不使用该选项，让整场游戏都保持“高牌获胜”模式；也可以一开始就立刻使用该选项，使整场游戏都遵循“低牌获胜”规则。

已知 Bessie 可以预测 Elsie 出牌的顺序，请确定 Bessie 最多能获得多少分。

输入格式

第一行输入整数 N（$2 \leq N \leq 50,000$）。 接下来的 N 行给出 Elsie 在游戏连续各轮中将要打出的牌。 注意：由此信息可以很容易确定 Bessie 拥有哪些牌。

输出格式

输出一行，表示 Bessie 最多能获得的分数。

4
1
8
4
3

3

提示

在该样例中，Bessie 手中必然有 2、5、6、7 四张牌，她最多能赢 3 分。例如，她可以先用某张牌战胜 1，然后将规则切换为“低牌获胜”，之后再赢两轮。 题目致谢：Austin Bannister 和 Brian Dean

标签: USACO|2015|Platinum

来源

USACO|2015|Platinum