P7838 "Wdoi-3" Night Sparrow Treating

After a whole day of hardships, Mystia finally welcomed the last guest of the day—Houraisan Kaguya. As the young lady of Eientei and the princess of the Lunar Capital, Kaguya has always been a huge challenge for Mystia, who runs an ordinary snack stall. Kaguya is extremely picky, so Mystia often finds it hard to satisfy her needs. Even worse, if Kaguya thinks Mystia’s hospitality is not good enough, the outcome for the Night Sparrow Diner may not be much better than being destroyed by Yuyuko. So the poor little night sparrow can only ask for your help.

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.

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

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

#### 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