시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 1869 | 933 | 748 | 50.746% |
욱제는 매일 세계사에 한 획을 그을만한 심각한 비결정론적 문제에 직면한다. 그렇다. 바로 저녁메뉴를 고르는 것이다. 매일 반복되는 중대한 선택에 지친 욱제는 N일 동안의 저녁메뉴를 미리 골라두기로 했다.
욱제는 N개의 중복되지 않는 메뉴들과 커다란 돌림판을 준비했다. 그러고는 돌림판을 N개의 칸으로 균일하게 나눈 뒤, N개의 메뉴를 각각 한 번씩 써넣었다. 하나의 칸에는 정확히 하나의 메뉴만 적히며, 하나의 메뉴는 정확히 하나의 칸에만 적힌다.
'돌려돌려~ 돌림판~'
따라서 욱제는 2N번 돌림판을 돌리면 N일 동안의 메뉴를 모두 정할 수 있게 된다! 욱제가 돌림판을 돌린 결과가 순서대로 주어진다. 돌림판에는 최대 몇 개의 스티커가 붙어있을 수 있을까?
첫째 줄에 메뉴의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 욱제가 뽑은 순서대로 해당 칸에 적힌 메뉴 번호가 주어진다. 메뉴는 1부터 N까지의 자연수로 주어진다. (1 ≤ 메뉴 ≤ N)
돌림판에 붙어있을 수 있는 스티커의 최대 개수를 출력한다.
3 1 3 3 2 1 2
2
5 1 1 2 2 3 3 4 4 5 5
1
High School > 선린인터넷고등학교 > 제1회 천하제일 코딩대회 예선 B번