#P6179. 纸牌游戏

纸牌游戏

题目描述

munrolashi123是纸牌游戏的忠实粉丝。对他而言,其他队员都算不上对手。更离谱的是,他能完全预测其他队员在打牌时的行为。尽管如此,munrolashi123知道取胜仍然是一个挑战。

munrolashi123和他的朋友 lishijun正在玩一种纸牌游戏。这个游戏里要用到一副 2N2N 张牌的套牌,编号从 112N2N。munrolashi123和 lishijun 每个人各分得 NN 张卡片。接下来进行 NN 轮比赛,munrolashi123 和 lishijun 每轮各出一张牌。每一轮谁的牌编号更大,谁就赢得了本轮的胜利。

munrolashi123 已经预测了 lishijun 的出牌顺序,请帮助 munrolashi123 算出他最多能赢多少轮。

输入格式

第一行一个整数 NN1N5×1041 \leq N \leq 5 \times 10^4)。

接下来 NN 行,第 ii 行一个整数,表示 lishijun 第 ii 轮出的牌。注意 munrolashi123 手中的 NN 张牌很容易从输入中推出。

输出格式

输出 munrolashi123 最多能赢多少轮。

3
1
6
4
2

提示

munrolashi123 手中拿着 2,3,52,3,5 三张牌。

它第一轮出 22,第二轮出 33,第三轮出 55,从而赢得一,三两轮。可以证明不存在更优的方案。