2200. [USACO Dec15]卡牌游戏(白金组)

【题目描述】

奶牛贝茜是卡牌游戏的狂热爱好者，但是令人吃惊的，她缺乏对手。不幸的是，任何牧群里的其他牛都不是好对手。

他们实在是太差了，实际上，他们玩卡牌游戏时会遵循一种完全可以被预测的模式。然而对于贝茜来说，找到赢的方法仍然是一个挑战。

贝茜和他的朋友埃尔西最近在玩一个简单的卡牌游戏，总共有$2N$张卡牌，上面的数字为$1\sim2N$, 贝茜分得$N$张，埃尔西分得$N$张。

他们玩$N$局游戏，每局游戏双方都出一张牌。

最初，数字大的得1分，输了不得分。但是，贝茜可以在游戏的某个时刻改变游戏规则（有且仅有一次），对于剩下的游戏，数字小的得1分，输了不得分。贝茜可以不做出这个选择，整局都是“高分卡片赢”，或者一开始就改变规则“低分卡片赢”。

给出贝茜预测的埃尔西将要使用的$N$张卡片，求出贝茜的得分最大值。

【输入格式】

第一行一个整数$n$;

接下来$n$行每行一个整数$x$,表示埃尔西拥有的卡片数字;

很简单就能推测出贝茜拥有的卡片;

【输出格式】

只有一行一个整数$max$,为得分最大值;

【样例输入】

4
1
8
4
3

【样例输出】

3

【提示】

这里，贝茜一定拥有卡片$2,5,6,7,$最多可以赢$3$分

以下是两种（不止两种$3$分方案）

     Elsie Bessie  Bessie Score

      1   <  2          1

     8   >  5          0

     4   <  6          1

     3   <  7          1

     no change rules(一直大者得分)

 Elsie Bessie  Bessie Score

    刚开始大者得分

    1   <  7          1

    change rules(从此之后小者得分)

    8   >  6          1

    4   >  2          1

    3   <  5          0     no change rules

【数据规模】

对于$13$%的数据，$n<=100$；

对于$20$%的数据, $n<=20000$；

对于$100$%的数据,$n<=50000$。

【来源】

USACO 2015 Dec HighCard Lowcard (Platinum)