레이팅 미적용위대한 소 화가 피카우소는 평범한 2차원 작품에 싫증이 났고 (게다가 다른 이들이 자신의 작품을 베끼는 것에 짜증도 나서), 더 미니멀한 1차원 스타일로 전향하기로 했다.
이제 그녀의 그림은 길이 \(N\) (\(1 \leq N \leq 100,000\))의 1차원 색 배열로 표현되지만, 그림을 그리는 방식은 이전과 같다. 빈 캔버스에서 시작하여 물감 "직사각형"들을 차례로 덧칠하는데, 1차원의 경우 직사각형은 단순히 구간이 된다. 그녀는 색 \(1 \ldots N\)을 각각 정확히 한 번씩 사용하며, 이전과 마찬가지로 일부 색은 끝에 가서는 완전히 덮여 버릴 수도 있다.
피카우소가 크게 낙담하게도, 경쟁자인 무네는 이 1차원 그림조차 베끼는 방법을 알아낸 듯하다. 무네는 앞선 문제와 비슷한 전략을 사용한다. 서로 겹치지 않는 구간들의 집합을 칠하고, 마를 때까지 기다린 뒤, 다시 서로 겹치지 않는 구간들의 집합을 칠하는 식이다. 무네는 전체 과정에서 각 색의 구간을 최대 한 번만 칠할 수 있다. 주어진 피카우소의 1차원 그림을 무네가 베끼는 데 필요한 라운드 수를 계산하라.
Problem credits: Brian Dean
Problem credits: Brian Dean
입력의 첫째 줄에 \(N\)이 주어지고, 다음 \(N\)개의 줄에 1차원 그림의 각 칸의 색을 나타내는 \(0 \ldots N\) 범위의 정수가 주어진다 (0은 빈 칸을 의미한다).
이 그림을 베끼는 데 필요한 최소 라운드 수를 출력한다. 만약 이 그림이 피카우소의 진품일 수 없다면 (즉, 각 색을 한 번씩 사용한 구간들을 층층이 덧칠하는 방식으로 그릴 수 없다면) -1을 출력한다.
art2.in · 출력을 쓸 파일 art2.out7
0
1
4
5
1
3
32In this example, the interval of color 1 must be painted in an earlier round
than the intervals of colors 4 and 5, so at least two rounds are needed.