자연수가 적힌 카드 \(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\) 사이 카드 수" 중 가장 큰 값을 구하는 프로그램을 작성하라.

• 주어지는 모든 수는 정수이다.
• \(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\)가 정확히 두 번 나타난다.

첫 번째 줄에 정수 \(N\)이 주어진다.

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

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 1차 대회 > 초등부 1번