34115번 - 먼 카드 서브태스크

문제

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

각 카드에는 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$이 주어진다.

두 번째 줄에 2ドルN$개의 정수 $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$가 정확히 두 번 나타난다.

서브태스크

힌트