## USACO 2015 December Contest, Gold

## Problem 1. High Card Low Card (Gold)

Contest has ended.

**Log in to allow submissions in analysis mode**

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. In the first $N/2$ rounds, the player with the highest card earns a point, and in the last $N/2$ rounds, the rules switch and the player who plays the lowest card wins a point.

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

#### INPUT FORMAT (file cardgame.in):

The first line of input contains the value of N ($2 \leq N \leq 50,000$; $N$ will be even).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 FORMAT (file cardgame.out):

Output a single line giving the maximum number of points Bessie can score.#### SAMPLE INPUT:

4 1 8 4 3

#### SAMPLE OUTPUT:

2

Here, Bessie must have cards 2, 5, and 6, and 7 in her hand, and she can use these to win at most 2 points, by saving her '2' card until one of the hands in the second half of the game.

Problem credits: Brian Dean