시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 759 229 185 48.556%

문제

욱제는 매일 세계사에 한 획을 그을만한 심각한 비결정론적 문제에 직면한다. 그렇다. 바로 저녁메뉴를 고르는 것이다.

매일 반복되는 중대한 선택에 지친 욱제는 N일 동안의 저녁메뉴를 미리 골라두기로 했다. 하지만 결정장애가 있는 욱제는 메뉴를 스스로 고르는 일에 큰 어려움을 느꼈다. 그래서 2N개의 공과 N개의 메뉴를 준비한 뒤 2개의 공에 같은 메뉴를 적고, 이미 번호가 적힌 공과 번호가 겹치지 않도록 공에 1~2N까지의 번호를 임의로 부여했다. 따라서 2N개의 공들은 1~2N까지 모두 다른 번호를 부여받게 된다.

욱제는 N일의 메뉴를 모두 정할 때까지 공을 번호 순서대로 확인한다. 공을 뽑았을 때 바구니에 같은 메뉴의 공이 이미 들어있다면, 뽑은 공과 이미 들어있는 공을 버린 뒤, 그 공에 적힌 메뉴로 저녁 메뉴를 순서대로 채워나간다. 같은 메뉴의 공이 들어있지 않다면, 바구니에 공을 넣고 계속 공을 뽑아나간다.

하지만 슬프게도 결정장애 말기 판정을 받은 욱제는 바구니의 크기마저도 스스로 고를 수가 없었다. 욱제를 도와주자! 욱제가 주어진 순서대로 공을 뽑았을 때, 바구니에는 최대 몇 개의 공이 동시에 존재할 수 있을까?

입력

첫째 줄에 메뉴의 개수 N이 주어진다. (1 <= N <= 100,000) 둘째 줄에 공의 번호 순서대로 해당하는 공에 적힌 메뉴가 주어진다. 편의상 메뉴는 1부터 N까지의 자연수로 표현되어 주어진다. (1 <= 메뉴 <= N)

출력

주어진 순서대로 공을 뽑았을 때, 바구니에 동시에 존재할 수 있는 공의 최대 갯수를 출력한다.

예제 입력

3
1 3 3 2 1 2

예제 출력

2

예제 입력 2

5
1 1 2 2 3 3 4 4 5 5

예제 출력 2

1

힌트

출처

High School > 선린인터넷고등학교 > 제1회 천하제일 코딩대회 예선 B번

  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 만든 사람: wookje