욱제의 저녁 메뉴 돌림판

시간 제한2초메모리 제한256 MB

요약

각 메뉴 번호가 정확히 두 번씩 나오는 수열이 주어질 때, 한 번만 나오고 아직 두 번 나오지 않은 값의 개수가 최대가 되는 지점을 구한다.

문제

욱제는 매일 저녁 메뉴를 고르느라 시간을 쓴다. 같은 고민을 매일 반복하기 싫어서 $N$ 일치 저녁 메뉴를 한 번에 정하기로 했다.

욱제는 서로 다른 메뉴 $N$ 개와 커다란 돌림판을 준비했다. 돌림판을 크기가 같은 칸 $N$ 개로 나눈 뒤 각 칸에 메뉴를 하나씩 적었다. 한 칸에는 메뉴가 정확히 하나 적히고, 한 메뉴는 정확히 한 칸에만 적힌다.

욱제는 다음 규칙으로 돌림판을 돌린다.

돌림판을 돌려서 걸린 칸을 확인한다.
걸린 칸에 스티커가 없으면 스티커를 하나 붙인다.
걸린 칸에 스티커가 있으면 그 칸에 적힌 메뉴를 식단표에 적고, 스티커를 뗀 뒤 그 칸을 제거한다. 욱제의 돌림판은 특별해서 제거된 칸에는 다시는 멈추지 않는다.
칸이 모두 제거될 때까지 1번부터 3번까지를 반복한다.

이 규칙이면 돌림판을 $2N$ 번 돌려서 $N$ 일치 메뉴가 모두 정해진다. 욱제가 돌림판을 돌린 결과가 순서대로 주어질 때, 돌림판에 스티커가 동시에 붙어 있던 최대 개수를 구하여라.

첫째 줄에 메뉴의 개수 $N$ 이 주어진다. ( $1 \le N \le 10^5$ )

둘째 줄에 욱제가 돌림판을 돌린 순서대로 걸린 칸에 적힌 메뉴 번호 $2N$ 개가 공백으로 구분되어 주어진다. 메뉴 번호는 $1$ 이상 $N$ 이하의 정수이고, 각 번호는 정확히 두 번씩 나온다.

돌림판에 스티커가 동시에 붙어 있던 최대 개수를 출력한다.