P3129 [USACO15DEC] High Card Low Card P

题目描述

奶牛 Bessie 是卡牌游戏的狂热爱好者，这相当令人惊讶，因为她没有灵活的手指。不幸的是，牛群中的其他奶牛都不是好的对手。事实上，她们的表现非常糟糕，总是以完全可预测的方式出牌！尽管如此，对 Bessie 来说，如何获胜仍然是一个挑战。

Bessie 和她的朋友 Elsie 正在玩一个简单的卡牌游戏。她们拿一副 $2N$ 张牌，方便地编号为 $1 \ldots 2N$，并将其分成 $N$ 张牌给 Bessie 和 $N$ 张牌给 Elsie。然后，两人进行 $N$ 轮游戏，每轮 Bessie 和 Elsie 各打出一张牌。最初，打出更高牌的玩家得一分。然而，在游戏中的某个时刻，Bessie 可以决定改变规则，使得在接下来的游戏中，打出更低牌的玩家得一分。Bessie 可以选择不使用这个选项，让整个游戏保持在“高牌获胜”模式，或者她也可以立即启用这个选项，让整个游戏遵循“低牌获胜”的规则。

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

输入格式

输入的第一行包含 $N$ 的值（$2 \leq N \leq 50,000$）。

接下来的 $N$ 行包含 Elsie 在游戏每轮中将要打出的牌。注意，从这些信息中可以很容易地确定 Bessie 手中的牌。

输出格式

输出一行，表示 Bessie 可以获得的最大分数。

输入输出样例 1

4
1
8
4
3

3

说明/提示

在这里，Bessie 手中的牌必须是 2、5、6 和 7，她最多可以利用这些牌赢得 3 分。例如，她可以先击败 1 这张牌，然后将规则切换为“低牌获胜”，之后她可以再赢得两轮。