Maximizing the Longest Consecutive Rating Sequence

There are 2n+1 ingredients arranged in a row, indexed from 1 to 2n+1 from left to right. Each ingredient has a distinct rating A_i chosen from the set \(\{1,2,\dots,2n+1\}\). These ingredients are the pre-selected ingredients.

Then, following a strange procedure, the final set of ingredients is chosen by repeatedly performing the following steps until exactly n+1 ingredients have been selected:

1. Assume the current list of candidate ingredients has size \(2k+1\). They are numbered 1 to \(2k+1\) (from left to right). Remove the ingredient in the middle, i.e. the \(k+1\)-th ingredient, and add it to the final set. (This removal is mandatory.)
2. If any ingredients remain, choose any one of them arbitrarily and remove it (this ingredient will not be in the final set). The remaining ingredients keep their order.

The satisfaction of a final selection is defined as follows. Let \(F\) be the final set of ingredients (of size \(n+1\)). Sort their ratings in increasing order to obtain \(S = \{s_1, s_2, \dots, s_{n+1}\}\). Then, the satisfaction is the length of the longest subsequence of \(S\) that forms a consecutive (i.e. arithmetic sequence with common difference 1) sequence. For example, if \(S = \{1,4,5,6,8,10,11\}\), then the longest consecutive subsequence is \(\{4,5,6\}\) with length 3.

It can be shown that by suitably choosing which ingredient to remove in step 2, the final set can always be made to be a contiguous segment of the original row. That is, one may achieve any contiguous block of n+1 ingredients from the original order. Under this observation, the problem reduces to the following:

Given the array \(A[1 \dots 2n+1]\), select a contiguous segment of length \(n+1\) (which is achievable by the removal process) so that when the ratings in that segment are sorted, the length of its longest consecutive sequence is maximized. Determine the maximum possible satisfaction.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(n\) (\(0 \leq n\)).

The second line contains \(2n+1\) integers \(A_1, A_2, \dots, A_{2n+1}\) — a permutation of \(\{1, 2, \dots, 2n+1\}\).

outputFormat

Output a single integer, the maximum satisfaction (i.e. the maximum length of a consecutive sequence of ratings) achievable by optimally choosing the free removals.

sample

1
2 1 3

2