#1210. 「USACO 2015.12 Gold」High Card Low Card (Gold)

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
cardgame.in ≫ cardgame.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

奶牛 Bessie 是卡牌游戏的狂热爱好者,尽管她没有对生拇指,但这并不影响她的热情。遗憾的是,她的同伴们在卡牌游戏方面水平堪忧,甚至出牌顺序都完全可预测!尽管如此,Bessie 仍需精心策划才能获胜。

Bessie 和她的朋友 Elsie 正在玩一个简单的卡牌游戏。她们使用一副包含 张卡牌的牌组(编号为 ),并将牌分成各 张。随后进行 轮比赛:每轮双方各打出一张牌。在前 轮中,打出较大数字的玩家得 1 分;在后 轮中,规则反转,打出较小数字的玩家得 1 分。

已知 Bessie 可以预知 Elsie 每轮出牌的顺序,请计算 Bessie 能够获得的最大分数。

输入格式 cardgame.in

第一行输入包含整数 ,且 为偶数)。

接下来 行按顺序给出 Elsie 在每轮比赛中将打出的卡牌。注意根据这些信息可以推断出 Bessie 手中的卡牌。

输出格式 cardgame.out

输出一行,包含 Bessie 能够获得的最大分数。

样例

输入 #1

4
1
8
4
3

输出 #1

2

数据范围与提示

在此样例中,Bessie 手中的卡牌为 。她可以通过在比赛后半段保留 这张牌,从而最多获得 2 分。

题目提供者:Brian Dean