Il y a $2N$ cartes portant des entiers strictement positifs. Elles sont disposées en ligne de gauche à droite.

Chaque carte porte exactement un entier strictement positif compris entre $1$ et $N$, bornes incluses. Soit $X_i$ le nombre sur la carte de position $i$ depuis la gauche ($1\le i\le2N$).

Pour chaque $k$ tel que $1\le k\le N$, exactement deux cartes portent $k$. Autrement dit, chaque entier strictement positif de $1$ à $N$ apparaît sur exactement deux cartes.

정올이 appelle le nombre de cartes situées entre les deux cartes portant l’entier strictement positif $k$ le « nombre de cartes entre $k$ ».

Par exemple, considérons la disposition de la figure ci-dessous. On a $N=4$ et $X_1=1,X_2=2,X_3=2,X_4=4,X_5=3,X_6=1,X_7=3,X_8=4$.

• Entre les deux cartes portant $1$ se trouvent, dans l’ordre, les cartes portant $2,2,4,3$ ; le nombre de cartes entre $1$ vaut donc $4$.
• Il n’y a aucune carte entre les deux cartes portant $2$ ; le nombre de cartes entre $2$ vaut donc $0$.
• Seule la carte portant $1$ se trouve entre les deux cartes portant $3$ ; le nombre de cartes entre $3$ vaut donc $1$.
• Entre les deux cartes portant $4$ se trouvent, dans l’ordre, les cartes portant $3,1,3$ ; le nombre de cartes entre $4$ vaut donc $3$.

Dans cet exemple, le plus grand nombre de cartes entre un quelconque $k$ est le nombre de cartes entre $1$, qui vaut $4$.

정올이 souhaite trouver le plus grand nombre de cartes entre $k$ pour tous les entiers strictement positifs $k$ de $1$ à $N$.

Étant donnés les nombres inscrits sur les cartes dans leur ordre, écrivez un programme qui trouve le plus grand nombre de cartes entre un quelconque $k$.

Contraintes

• Tous les nombres donnés sont entiers.
• $1\le N\le2\,000$
• Pour tout $i$ ($1\le i\le2N$): $1\le X_i\le N$
• Pour tout $k$ ($1\le k\le N$), ce nombre apparaît exactement deux fois dans $X_1,X_2,\ldots,X_{2N}$.

Sous-tâches

1. (10 points) $N\le2$
2. (15 points) La réponse est $0$ ou $1$.
3. (15 points) La réponse est $2N-3$ ou $2N-2$.
4. (20 points) $N\le500$
5. (40 points) Aucune contrainte supplémentaire.

Entrée

La première ligne contient l’entier $N$.

La deuxième ligne contient $2N$ entiers $X_1,X_2,\ldots,X_{2N}$ séparés par des espaces.

Sortie

Affichez la réponse sur la première ligne.

Exemples

Entrée 1

4
1 2 2 4 3 1 3 4

Sortie 1

4

Entrée 2

4
1 2 3 4 4 3 2 1

Sortie 2

6