High Card Low Card

Bessie the cow loves card games, which is a surprising hobby for an animal with no opposable thumbs. The trouble is that none of the other cows in the herd make decent opponents. They play so badly that their order of play is completely predictable. Even then, finding a winning line is not easy for Bessie.

Bessie and her friend Elsie play a simple card game. They take a deck of $2N$ cards numbered $1$ through $2N$ and split it so that Bessie holds $N$ cards and Elsie holds $N$ cards. They play $N$ rounds, and in each round each player puts down one card. In the first $N/2$ rounds the player with the higher card scores one point. In the last $N/2$ rounds the rule flips and the player with the lower card scores one point. All card numbers are distinct, so no round is a tie.

Bessie knows in advance the order in which Elsie will play her cards. Bessie may play her own cards in any order she likes. Write a program that computes the maximum number of points Bessie can score.

The first line contains $N$ ($2 \le N \le 50000$, and $N$ is even).

Each of the next $N$ lines contains one card that Elsie plays, given in round order. The cards missing from this list are exactly Bessie's hand.

Print the maximum number of points Bessie can score on a single line.

In the example with $N = 4$ where Elsie plays $1$, $8$, $4$, $3$, Bessie holds $2$, $5$, $6$, and $7$. She beats the $1$ with her $5$ in the first round, then saves the $2$ for one of the last two rounds, where it beats the $4$ or the $3$. Two points is the most she can get.