문제

기존의 2차원 예술에 실증을 느낀 예술가 민영이는 더욱 단순한 1차원 스타일로 전향하기로 했다.

민영이의 그림은 길이가 $N$ ($1 \le N \le 100\,000$)인 1차원 색상 배열로 설명할 수 있다. 민영이의 예술 방식은 이전과 같다. 민영이는 빈 캔버스에서 시작하여, 그 위에 구간 단위로 페인트를 차례대로 덧칠하는 방식으로 그림을 그린다. 민영이는 $1, \dots, N$까지의 색상을 각각 정확히 한 번씩 사용하며, 나중에 칠해진 색이 이전의 색을 완전히 덮어버릴 수도 있다.

민영이의 라이벌 준모는 이 1차원 그림을 복제하는 방법을 알아냈다. 준모는 다음과 같은 전략을 사용한다.

1. 서로 겹치지 않는 구간들의 집합을 선택하여 색을 칠한다.
2. 페인트가 마를 때까지 기다린다.
3. 다시 서로 겹치지 않는 구간들의 집합을 선택하여 덧칠하는 과정을 반복한다.

준모는 전체 과정 동안 각 색상에 대해 최대 한 번의 구간만 칠할 수 있다. 민영이가 그린 1차원 그림이 주어졌을 때, 준모가 이 그림을 똑같이 복제하기 위해 필요한 최소 라운드 수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$이 주어진다. ($1 \le N \le 100\,000$) 이어서 $N$개의 줄에 걸쳐 1차원 그림의 각 칸에 해당하는 색상 정보가 정수로 주어진다. 색상은 $0$ 이상 $N$ 이하의 범위를 가지며, $0$은 페인트가 칠해지지 않은 빈 칸을 의미한다.

출력

그림을 복제하기 위해 필요한 최소 라운드 수를 출력한다. 만약 민영이가 한 색상당 하나의 구간을 덧칠하는 방식으로는 이 그림을 절대 만들 수 없다면 -1을 출력한다.

예제 입력 1

7
0
1
4
5
1
3
3

예제 출력 1

2