High Card Wins

题目描述

奶牛 Bessie 非常喜欢纸牌游戏，这一点相当令人惊讶，因为她没有灵活的对握拇指。不幸的是，牛群里的其他奶牛都不是好对手。她们差劲到总是以完全可预测的方式出牌！尽管如此，Bessie 仍然可能难以判断如何获胜。

Bessie 和她的朋友 Elsie 目前在玩一个简单的纸牌游戏：她们取一副包含 $2N$ 张牌的牌组，牌面编号为 $1 \ldots 2N$，并将其分成两份，Bessie 得到 $N$ 张牌，Elsie 得到 $N$ 张牌。随后她们进行 $N$ 轮游戏，每一轮中 Bessie 和 Elsie 各出一张牌，牌面更大的玩家获得 1 分。

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

输入格式

第一行输入整数 N（$1 \leq N \leq 50,000$）。 接下来 N 行给出 Elsie 在游戏每一轮中依次打出的牌。注意：从这些信息中可以很容易确定 Bessie 拥有的牌。

输出格式

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

3
1
6
4

2

提示

这里，Bessie 手中一定有 2、3、5 三张牌；她最多能赢 2 分，一种方法是把 5 留到最后用来击败 Elsie 的 4。 题目贡献：Austin Bannister 和 Brian Dean

标签: USACO|2015|Silver

来源

USACO|2015|Silver