저장 공간 조각화

펠릭스는 차고에서 스타트업 프로젝트를 만들고 있다. 이름은 이미 SuperFastZilla로 정했다. 이 프로그램이 무슨 일을 할지는 아직 정하지 못했지만, 아주 빠르게 동작해야 한다는 점만은 확실하다.

어느 날 펠릭스는 빠른 알고리즘을 쓰는데도 SuperFastZilla가 너무 느리다는 사실을 알아차렸다. 펠릭스는 저장 공간이 조각나 있는 것을 원인으로 본다.

SuperFastZilla가 쓰는 저장 공간은 메모리 블록 $n$개로 이루어져 있다. 블록 하나는 연산 하나에만 쓰이고, $i$번째 블록은 $a_i$번째 연산에 쓰인다.

펠릭스는 블록을 자신이 쓰이는 연산 번호 순서로 정렬하려고 한다. 이 작업을 빠르게 하려고 저장 공간을 연속한 블록으로 이루어진 구간 여러 개로 자르고, 구간의 순서만 바꿔서 정렬된 배열을 만든다. 자르는 위치는 마음대로 고를 수 있고, 잘라 낸 구간은 어떤 순서로든 다시 이어 붙일 수 있다. 구간 안에서 블록의 순서는 바꾸지 못한다. 다시 이어 붙인 뒤 연산 번호는 감소하지 않는 순서여야 한다.

구간의 개수를 가장 적게 하는 방법을 찾아 그 최소 개수를 구하라.

예를 들어 $a = [2, 3, 1, 1, 2, 2, 1]$이면 $[2, 3]$, $[1, 1, 2, 2]$, $[1]$의 세 구간으로 자른 다음 $[1]$, $[1, 1, 2, 2]$, $[2, 3]$ 순서로 이어 붙여 정렬된 배열을 얻는다. 두 구간으로는 만들 수 없으므로 최소 개수는 3이다.

첫째 줄에 블록의 개수 $n$이 주어진다. ($1 \le n \le 10^5$)

둘째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 10^5$)

필요한 구간의 최소 개수를 한 줄에 출력한다.