Description

To serve this distinguished guest, Mystia prepared $2n+1$ kinds of ingredients in advance and lined them up in a row. The $i$-th ingredient is at the $i$-th position from the left, and is called a preselected ingredient.

Then, Kaguya scored all ingredients. Each ingredient is given a distinct score in $[1,2n+1]$. The score of the $i$-th ingredient is $A_i$.

Because of the Lunarians’ strange preferences, Kaguya likes a set of consecutive numbers. Therefore, her satisfaction with the finally chosen ingredients (call them the final ingredients) is defined as follows: after sorting these ingredients by score in increasing order, take the length of the longest subsequence whose scores are consecutive. “Consecutive” means the scores form an arithmetic progression with common difference $1$. For example, in $\{1,4,5,6,8,10,11\}$, the longest consecutive-score sequence that can be selected is $\{4,5,6\}$, so for this plan, Kaguya’s satisfaction is $3$.

However, Kaguya, who enjoys watching others suffer, decided to torment Mystia with a bizarre selection method:

1. Suppose there are currently $2k+1$ ingredients. They are lined up in order, and Mystia numbers them from left to right as $1,2,3\cdots (2k+1)$.
2. Mystia selects the ingredient at the middle position (i.e., the ingredient numbered $k+1$) and adds it to the final ingredients. Note that any ingredient added to the final ingredients is removed from the candidate ingredients.
3. Mystia arbitrarily chooses one ingredient among the candidate ingredients and removes it. The relative order of the remaining ingredients stays the same. In particular, if the candidate ingredients are already empty, Mystia does nothing.

Mystia repeats operations $1\sim 3$ until there are exactly $n+1$ ingredients in the final ingredients. She wants to know: under an optimal strategy, what is the maximum satisfaction Kaguya can obtain.

Input Format

The first line contains an integer $n$.

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

Output Format

Output one integer on a single line, representing the maximum satisfaction obtainable under an optimal strategy.

3
4 7 3 6 1 2 5

3

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

8

1
1 2 3

2

Hint

Explanation for Sample 1

$$\def\arraystretch{1.7} \begin{array}{|c|c|c|c|}\hline \textbf{Candidate Ingredients} & \textbf{Select} & \textbf{Delete} & \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 time, the longest consecutive ingredients in the final ingredients are $\{2,3,4\}$, with length $3$. It can be proven that there is no better plan.

---

Constraints and Notes

$$\def\arraystretch{1.7} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{Special Property} & \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: it is guaranteed that $\forall i\in[1,2n+1]$, $A_i=i$. Sample 3 satisfies this property.
• For $100\%$ of the testdata, $1 \leq n \leq 2 \times 10^5$, and $A$ is a permutation of $1 \sim 2n+1$.

Translated by ChatGPT 5