정렬

수열 $A_1, A_2, \dots, A_N$이 모든 $1 \le i < N$에 대해 $A_i \le A_{i+1}$을 만족하면 이 수열을 정렬된 수열이라고 한다.

다음 방법으로 수열을 정렬하려고 한다. 먼저 수열을 $M$개의 구간으로 나눈다. 수열의 처음 $k_1$개 원소가 첫 번째 구간을, 다음 $k_2$개 원소가 두 번째 구간을 이루며, 이런 식으로 마지막 $k_M$개 원소가 마지막 구간을 이룬다. 그다음 구간 전체를 서로 교환할 수 있지만, 구간 안에서는 원소의 순서를 바꿀 수 없다.

구간을 어떻게 나누느냐에 따라 구간 교환만으로 수열을 정렬할 수도 있고 없을 수도 있다. 예를 들어 수열 전체를 한 구간으로 두면, 처음부터 정렬되어 있던 수열만 정렬할 수 있다. 원소가 $N$개인 수열은 $N$개의 구간으로 나누면 항상 정렬할 수 있다.

구간 교환만으로 수열을 정렬할 수 있도록 하는 최소 구간 개수 $M$을 구하라.

첫 번째 줄에 수열의 원소 개수 $N$($1 \le N \le 500\,000$)이 주어진다. 두 번째 줄에는 수열의 원소 $A_1, A_2, \dots, A_N$($1 \le A_i \le N$)이 공백으로 구분되어 주어진다.

구간 교환으로 수열을 정렬할 수 있게 하는 최소 구간 개수 $M$을 한 줄에 출력한다.