Problem Background

After a day of hardships, Mystia finally welcomes her last guest of the day—Hakurei Reimu. As the mistress of the Eientei and the princess of the Lunar Capital, Reimu has always been a significant challenge for Mystia, who runs a humble food stall. Reimu's taste is extremely picky, making it often difficult for Mystia to meet her demands. Even more troublesome is that if Reimu feels that Mystia's service is inadequate, the consequences for the Night Sparrow食堂 might not be much better than being destroyed by Yuyuko.

So, the poor Night Sparrow has to seek your help.

Problem Description

To serve this important guest, Mystia has prepared $2n+1$ ingredients in advance and arranged them in a row, with the $i$-th ingredient in the $i$-th position from the left, as the preliminary ingredients.

Next, Reimu scores all the ingredients, each being given a unique score within the range $[1, 2n+1]$. The score of the $i$-th ingredient is $A_i$.

Due to the peculiar preferences of the Lunar inhabitants, Reimu likes a set of consecutive numbers. Therefore, her satisfaction with the final selection of ingredients (let's call them final ingredients) is defined as the length of the longest sequence of ingredients whose scores are consecutive when sorted in ascending order. Consecutive scores mean that the scores form an arithmetic sequence with a common difference of 1. For example, in the set $\{1, 4, 5, 6, 8, 10, 11\}$, the longest consecutive sequence that can be picked is $\{4, 5, 6\}$, so Reimu's satisfaction for this scheme is $3$.

However, Reimu, who enjoys watching the spectacle, decides to use an unusual selection method to torment Mystia—

1. Suppose there are currently $2k+1$ ingredients. These ingredients are arranged in order, and Mystia numbers them from left to right as $1, 2, 3, \cdots, (2k+1)$.
2. Mystia selects the ingredient currently in the middle position (i.e., the ingredient numbered $k+1$) and adds it to the final ingredients. Note that the added ingredient will be removed from the preliminary ingredients.
3. Mystia arbitrarily selects one ingredient from the preliminary ingredients and removes it, maintaining the relative positions of the remaining ingredients. Specifically, if the preliminary ingredients are empty, Mystia does nothing.

Mystia will repeatedly perform operations $1\sim3$ until there are exactly $n+1$ ingredients in the final ingredients. She wants to know the maximum satisfaction Reimu can achieve if she follows the optimal operation plan.

Input Format

The first line contains an integer $n$.

The second line contains $2n+1$ integers, representing the scores of each ingredient.

Output Format

A single line containing an integer, representing the maximum satisfaction that can be achieved with the optimal operation plan.

Sample Input and Output

Sample Input #1

3
4 7 3 6 1 2 5

Sample Output #1

3

Sample Input #2

7
1 15 2 14 3 13 4 12 5 11 6 10 7 9 8

Sample Output #2

8

Sample Input #3

1
1 2 3

Sample Output #3

2

Notes

Sample 1 Explanation

$$ \def{\arraystretch}{1.7} \begin{array}{|c|c|c|c|}\hline \textbf{Preliminary Ingredients} & \textbf{Selection} & \textbf{Deletion} & \textbf{Final Ingredients} \cr\hline 4,7,3,6,1,2,5 & 6 & 1 & 6\cr \hline 4,7,3,2,5 & 3 & 7 & 3,6\cr \hline 4,2,5 & 2 & 5 & 2,3,6\cr \hline 4 & 4 & - & 2,3,4,6\cr \hline \end{array} $$

At this point, the longest consecutive sequence of ingredients in the final ingredients is $\{2,3,4\}$, with a length of $3$. It can be proven that there is no better solution.

Data Range and Constraints

$$ \def{\arraystretch}{1.7} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{Special Properties} & \textbf{Score} \cr\hline 1 & 5 & - & 10\cr\hline 2 & 200 & - & 15\cr\hline 3 & 800 & - & 15\cr\hline 4 & 5\times 10^3 & - & 20\cr\hline 5 & 2\times 10^5 & \text{A} & 5\cr\hline 6 & 2\times 10^5 & - & 35\cr\hline \end{array} $$

• Special Property A: Guarantees that $\forall i \in [1, 2n+1]$, $A_i = i$. Sample 3 satisfies this property.
• For $100\%$ of the data, $1 \leq n \leq 2 \times 10^5$, and $A$ is a permutation of $1 \sim 2n+1$.

见题面 Input 部分

见题面 Output 部分