P3129 [USACO15DEC] High Card Low Card P

题目描述

A 和 B 玩游戏。有一副 $2N$ 张牌，编号为 $1 \ldots 2N$，并将其分成 $N$ 张牌给 A 和 $N$ 张牌给 B。

然后，两人进行 $N$ 轮游戏，每轮 A 和 B 各打出一张牌。最初，打出更高牌的玩家得一分。

已知 B 出牌的顺序。

在游戏中的某个时刻，A 可以决定改变规则，使得在接下来的游戏中，打出更低牌的玩家得一分。

A 可以选择不使用这个选项，让整个游戏保持在“高牌获胜”模式，或者她也可以立即启用这个选项，让整个游戏遵循“低牌获胜”的规则。

请确定 A 可以获得的最大分数。

输入格式

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

下来的 $N$ 个整数，表示 B 每次出的牌。

输出格式

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

输入输出样例 #1

输入 #1

4
1
8
4
3

输出 #1

3

说明/提示

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