현대 미술 2

일반적인 2차원 작품에 지루함을 느끼고, 작품을 복사하는 사람들에게 좌절감을 느낀 위대한 예술가 미진은 좀 더 미니멀리스트하고 1차원적인 스타일로 전환하기로 결정했습니다.

그녀의 그림은 이제 길이가 $N$ ($1 \leq N \leq 100,000$)인 1차원 색상 배열로 설명할 수 있지만, 빈 캔버스에서 시작하여 그 위에 일련의 "사각형" 물감을 겹쳐서 칠하는 그녀의 그림 스타일은 동일하게 유지됩니다: (이 1차원의 경우 단순히 간격을 말한다.)

그녀는 이전과 마찬가지로 각의 색상 $1 \ldots N$을 정확히 한 번씩 사용하지만, 기존처럼 일부 색상은 마지막에 완전히 덮여질 수 있습니다.

그녀의 경쟁자인 민수는 이와 같은 미진의 1차원 그림까지 모사하는 방법을 찾아냈습니다. 그는 이전 문제와 같은 전략을 사용해 볼것입니다: 민수는 서로 겹치지 않는 일련의 간격에 그림을 그리고, 건조하고 다시 그림을 그리게 됩니다. 그리고 이 과정은 계속됩니다. 민수은 전체 과정 동안 각 색상의 간격을 최대 한 번만 칠할 수 있습니다. 주어진 미진의 1차원 그림을 모사하는 데 필요한 라운드 횟수를 계산해 주세요.

입력의 첫 번째 줄에는 $N$이 있고, 다음 $N$ 줄에는 1차원 그림의 각 셀의 색상을 나타내는 $0 \ldots N$ 범위의 정수가 포함됩니다 (0은 빈 셀을 나타냅니다).

이 그림을 모사하는 데 필요한 라운드의 최소 횟수를 출력하거나, 이것이 미진의 진품이 아닐 경우(-즉, 그녀가 각 색상을 하나씩 겹쳐서 칠할 수 없는 경우) -1을 출력하십시오.