60000 먼 카드 Silver V

문제

자연수가 적힌 카드 $2N$장이 있다. 이 카드들은 일렬로 왼쪽에서 오른쪽으로 나열되어 있다.

각 카드에는 $1$ 이상 $N$ 이하의 자연수가 정확히 하나씩 적혀 있다. 왼쪽에서 $i$ ($1 ≤ i ≤ 2N$)번째에 놓인 카드에 적힌 자연수를 $X_i$ 라고 하자.

$1 ≤ k ≤ N$인 각 $k$에 대해, $k$가 적힌 카드는 정확히 두 장이다. 즉, $1$부터 $N$까지의 각 자연수는 정확히 두 장의 카드에 적혀 있다.

정올이는 자연수 $k$가 적힌 두 카드 사이에 놓인 카드의 개수를 ”$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$, $4$, $3$이 적힌 카드가 있으므로, ”$1$ 사이 카드 수”는 $4$이다.
• $2$가 적힌 두 카드 사이에는 아무 카드도 없으므로, ”$2$ 사이 카드 수”는 $0$이다.
• $3$이 적힌 두 카드 사이에는 $1$이 적힌 카드만 있으므로, ”$3$ 사이 카드 수”는 $1$이다.
• $4$가 적힌 두 카드 사이에는 차례로 $3$, $1$, $3$이 적힌 카드가 있으므로, ”$4$ 사이 카드 수”는 $3$이다.

위의 사례에서 ”$k$ 사이 카드 수”들 중 가장 큰 것은 ”$1$ 사이 카드 수”로, 그 값은 $4$이다.

정올이는 $1$부터 $N$까지의 모든 자연수 $k$에 대한 ”$k$ 사이 카드 수” 중 가장 큰 값을 구하고 싶다.

카드가 나열된 순서대로 카드에 적힌 자연수가 주어질 때, 모든 ”$k$ 사이 카드 수” 중 가장 큰 값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 $2N$개의 정수 $X_1 , X_2 , \cdots, X_{2N}$이 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에 답을 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ N ≤ 2\, 000$
• $1 ≤ i ≤ 2N$인 각 $i$에 대해, $1 ≤ X_i ≤ N$
• $1 ≤ k ≤ N$인 각 $k$에 대해, $k$가 적힌 카드는 정확히 두 장이다. 즉, $X_1 , X_2 , \cdots, X_{2N}$ 중에서 $k$가 정확히 두 번 나타난다.

서브태스크

번호	배점	제한
1	10	$N ≤ 2$
2	15	답은 $0$ 또는 $1$이다.
3	15	답은 $2N − 3$ 또는 $2N − 2$이다.
4	20	$N ≤ 500$
5	40	추가 제약 조건 없음.

4
1 2 2 4 3 1 3 4

4

4
1 2 3 4 4 3 2 1

6