High Card Low Card (Gold)

题目描述

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

Bessie 和她的朋友 Elsie 正在玩一个简单的纸牌游戏：她们取一副包含 $2N$ 张牌的牌堆，方便起见将其编号为 $1 \ldots 2N$，并将其分成 Bessie 的 $N$ 张牌与 Elsie 的 $N$ 张牌。随后进行 $N$ 轮游戏，每一轮 Bessie 与 Elsie 都各出一张牌。在前 $N/2$ 轮中，出牌点数较高的玩家获得 1 分；在后 $N/2$ 轮中，规则切换为出牌点数较低的玩家获得 1 分。

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

输入格式

第一行输入一个整数 N（$2 \leq N \leq 50,000$；$N$ 为偶数）。

接下来 N 行给出 Elsie 在游戏每一轮依次打出的牌。 注意：根据这些信息很容易确定 Bessie 手中的牌。

输出格式

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

4
1
8
4
3

2

提示

这里，Bessie 手中必然有 2、5、6 和 7 这四张牌，她最多只能赢 2 分：方法是将她的“2”留到比赛后半段的某一手再出。

题目来源：Brian Dean

标签: USACO|2015|Gold

来源

USACO|2015|Gold