题目描述

Bessie the cow is a hu e fan of card games, which is quite surprising, given her lack of opposable thumbs. Unfortunately, none of the other cows in the herd are good opponents. They are so bad, in fact, that they always play in a completely predictable fashion! Nonetheless, it can still be a challenge for Bessie to figure out how to win.

Bessie and her friend Elsie are currently playing a simple card game where they take a deck of $2N$ cards, conveniently numbered $1 \ldots 2N$, and divide them into $N$ cards for Bessie and $N$ cards for Elsie. The two then play $N$ rounds, where in each round Bessie and Elsie both play a single card. Initially, the player who plays the highest card earns a point. However, at one point during the game, Bessie can decide to switch the rules so that for the rest of the game, the player who plays the lowest card wins a point. Bessie can choose not to use this option, leaving the entire game in "high card wins" mode, or she can even invoke the option right away, making the entire game follow the "low card wins" rule.

Given that Bessie can predict the order in which Elsie will play her cards, please determine the maximum number of points Bessie can win.

贝西很喜欢玩一种纸牌游戏。

贝西和她的朋友艾尔西正在玩这个简单的纸牌游戏。游戏有 $2N$ 张牌，牌上的数字是 $1$ 到 $2N$。把这些牌分成两份，贝西有 $N$ 张，艾尔西有另外 $N$ 张。接下来她们进行 $N$ 轮出牌，每次各出一张牌。一开始，谁出的牌上的数字大，谁就获得这一轮的胜利。贝西有一个特殊权利，她可以在任意一个时刻把原本数字大的获胜的规则改成数字小的获胜，这个改变将会一直持续到游戏结束。特别的，贝西可以从第一轮开始就使用小牌获胜的规则，也可以直到最后一轮都还杂使用大牌获胜的规则。

现在，贝西已经知道了艾尔西出牌的顺序，她想知道她最多能够赢多少轮。

输入格式

The first line of input contains the value of N ($2 \leq N \leq 50,000$).

The next N lines contain the cards that Elsie will play in each of the

successive rounds of the game. Note that it is easy to determine Bessie's cards

from this information.

输出格式

Output a single line giving the maximum number of points Bessie can score.

4
1
8
4
3

3

提示

Here, Bessie must have cards 2, 5, and 6, and 7 in her hand, and she can use

these to win at most 3 points. For example, she can defeat the 1 card and then

switch the rules to "low card wins", after which she can win two more rounds.