Predictable Card Game

Bessie the cow loves card games even though she lacks opposable thumbs. In this game, a deck of $2N$ cards numbered $1\ldots2N$ is split into $N$ cards for Bessie and $N$ cards for Elsie. They play $N$ rounds: in the first $\frac{N}{2}$ rounds the higher card wins the round, and in the last $\frac{N}{2}$ rounds the lower card wins.

Bessie knows the exact order in which Elsie will play her cards. Using this information, Bessie can choose how to play her own cards in order to maximize her total number of winning rounds. In each round, both players select one card from their hand. In the first half of the rounds, if Bessie's card is greater than Elsie’s card she wins the round; in the second half, if Bessie’s card is lower than Elsie’s she wins the round. Bessie may rearrange the order in which she plays her cards in each phase.

Your task is to help Bessie determine the maximum number of rounds she can win. Note that Bessie’s hand consists of all the cards in $\{1, 2, \ldots, 2N\}$ that Elsie does not have. You may assume that $N$ is even.

inputFormat

The first line of input contains a single even integer $N$ ($2 \le N \le 50000$). The following $N$ lines each contain a single integer, giving the sequence of cards that Elsie will play in order. All card values are distinct and lie in the range $1\ldots2N$.

outputFormat

Output a single integer: the maximum number of rounds Bessie can win by playing optimally.

sample

4
1
8
4
7

3