원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
먼 카드
원제: 먼 카드
문제
자연수가 적힌 카드 장이 있다. 이 카드들은 일렬로 왼쪽에서 오른쪽으로 나열되어 있다.
각 카드에는 이상 이하의 자연수가 정확히 하나씩 적혀 있다. 왼쪽에서 ()번째에 놓인 카드에 적힌 자연수를 라고 하자.
인 각 에 대해, 가 적힌 카드는 정확히 두 장이다. 즉, 부터 까지의 각 자연수는 정확히 두 장의 카드에 적혀 있다.
정올이는 자연수 가 적힌 두 카드 사이에 놓인 카드의 개수를 " 사이 카드 수"라고 부르기로 했다.
예를 들어, 아래 그림과 같이 카드가 놓여있다고 생각해 보자. 아래 그림에서 이고, , , , , , , , 이다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
- 이 적힌 두 카드 사이에는 차례로 , , , 이 적힌 카드가 있으므로, " 사이 카드 수"는 이다.
- 가 적힌 두 카드 사이에는 아무 카드도 없으므로, " 사이 카드 수"는 이다.
- 이 적힌 두 카드 사이에는 이 적힌 카드만 있으므로, " 사이 카드 수"는 이다.
- 가 적힌 두 카드 사이에는 차례로 , , 이 적힌 카드가 있으므로, " 사이 카드 수"는 이다.
위의 사례에서 " 사이 카드 수"들 중 가장 큰 것은 " 사이 카드 수"로, 그 값은 이다.
정올이는 부터 까지의 모든 자연수 에 대한 " 사이 카드 수" 중 가장 큰 값을 구하고 싶다.
카드가 나열된 순서대로 카드에 적힌 자연수가 주어질 때, 모든 " 사이 카드 수" 중 가장 큰 값을 구하는 프로그램을 작성하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 인 각 에 대해,
- 인 각 에 대해, 가 적힌 카드는 정확히 두 장이다. 즉, , , , 중에서 가 정확히 두 번 나타난다.
부분문제
- (10점)
- (15점) 답은 또는 이다.
- (15점) 답은 또는 이다.
- (20점)
- (40점) 추가 제약 조건 없음.
입력 형식
첫 번째 줄에 정수 이 주어진다.
두 번째 줄에 개의 정수 , , , 이 공백을 사이에 두고 주어진다.
출력 형식
첫 번째 줄에 답을 출력한다.
예제
예제 1
4 1 2 2 4 3 1 3 4
4
예제 2
4 1 2 3 4 4 3 2 1
6