현대 미술 2

평범한 2차원 그림에 싫증이 난 데다 다른 이가 자기 작품을 베끼는 데 지친 위대한 소 화가 Picowso는 더 미니멀한 1차원 화풍으로 바꾸기로 했다.

이제 Picowso의 그림은 길이가 $N$ ($1 \leq N \leq 100\,000$)인 1차원 색 배열로 나타낼 수 있지만, 그리는 방식은 그대로다. 빈 캔버스에서 시작해 물감으로 된 "직사각형"을 차례로 겹쳐 칠하는데, 1차원에서는 이 직사각형이 곧 구간이다. 색 $1, 2, \ldots, N$을 각각 정확히 한 번씩 쓰며, 이전과 마찬가지로 어떤 색은 마지막에 완전히 가려져 보이지 않을 수도 있다.

안타깝게도 경쟁자 Moonet은 이 1차원 그림마저 베끼는 법을 알아낸 듯하다. 방법은 앞 문제와 비슷하다. Moonet은 서로 겹치지 않는 구간 여러 개를 칠하고 마를 때까지 기다린 뒤, 다시 서로 겹치지 않는 구간 여러 개를 칠하는 과정을 되풀이한다. 한 번 칠하고 마를 때까지 기다리는 과정을 한 라운드라 한다. 전체 과정에서 Moonet은 각 색의 구간을 최대 하나만 칠할 수 있다.

Picowso의 1차원 그림이 주어질 때, Moonet이 이 그림을 베끼는 데 필요한 라운드 수를 구하여라.

첫째 줄에 $N$이 주어진다. 다음 $N$개의 줄에는 1차원 그림의 각 칸의 색을 나타내는 $0$ 이상 $N$ 이하의 정수가 하나씩 주어진다. $0$은 빈 칸을 뜻한다.

이 그림을 베끼는 데 필요한 최소 라운드 수를 출력한다. 이 그림이 Picowso의 진품일 수 없다면, 즉 Picowso가 색마다 구간을 하나씩 차례로 겹쳐 칠하는 방식으로는 이 그림을 그릴 수 없다면 $-1$을 출력한다.

예제에서 색 $1$의 구간은 색 $4$와 색 $5$의 구간보다 앞선 라운드에 칠해야 하므로 적어도 두 라운드가 필요하다.