正整数が書かれたカードが $2N$ 枚あります。これらは左から右へ一列に並んでいます。
各カードには $1$ 以上 $N$ 以下の正整数がちょうど 1 つ書かれています。左から $i$（$1\le i\le2N$）番目のカードに書かれた数を $X_i$ とします。
$1\le k\le N$ を満たす各 $k$ について、$k$ が書かれたカードはちょうど 2 枚あります。つまり、$1$ から $N$ までの各正整数はちょうど 2 枚のカードに書かれています。
정올이 は、正整数 $k$ が書かれた 2 枚のカードの間にあるカードの枚数を「$k$ の間のカード数」と呼ぶことにしました。
例えば、下図のような並びを考えます。図では $N=4$ で、$X_1=1,X_2=2,X_3=2,X_4=4,X_5=3,X_6=1,X_7=3,X_8=4$ です。
- $1$ の 2 枚の間には順に $2,2,4,3$ が書かれたカードがあるので、「$1$ の間のカード数」は $4$ です。
- $2$ の 2 枚の間にはカードがないので、「$2$ の間のカード数」は $0$ です。
- $3$ の 2 枚の間には $1$ のカードだけがあるので、「$3$ の間のカード数」は $1$ です。
- $4$ の 2 枚の間には順に $3,1,3$ が書かれたカードがあるので、「$4$ の間のカード数」は $3$ です。
この例では「$k$ の間のカード数」の最大値は「$1$ の間のカード数」で、その値は $4$ です。
정올이 は、$1$ から $N$ までのすべての正整数 $k$ に対する「$k$ の間のカード数」の最大値を求めたいと考えています。
カードに書かれた正整数が並び順に与えられます。「$k$ の間のカード数」の最大値を求めるプログラムを作成してください。
制約
- 与えられる数はすべて整数です。
- $1\le N\le2\,000$
- 各 $i$ ($1\le i\le2N$): $1\le X_i\le N$
- 各 $k$ ($1\le k\le N$), その数はちょうど 2 回現れます。対象の列は $X_1,X_2,\ldots,X_{2N}$.
小課題
- (10 点) $N\le2$
- (15 点) 答えは $0$ または $1$.
- (15 点) 答えは $2N-3$ または $2N-2$.
- (20 点) $N\le500$
- (40 点) 追加の制約はありません。
入力
1 行目に整数 $N$ が与えられます。
2 行目に $2N$ 個の整数 $X_1,X_2,\ldots,X_{2N}$ が空白で区切られて与えられます。
出力
1 行目に答えを出力してください。
入出力例
入力 1
4 1 2 2 4 3 1 3 4
出力 1
4
入力 2
4 1 2 3 4 4 3 2 1
出力 2
6