쉬는 시간의 돌

나이가 들수록 최신 유행을 따라가기가 어려워진다. 최근 초등학교를 휩쓸고 있는 놀라운 유행이 하나 있는데, 어린아이들이 종이보다도, 가위보다도 돌을 더 좋아한다는 것이다. 쉬는 시간이 끝나면 프리즈 선생님은 반 학생들을 모아야 한다. 교실로 돌아가기 전에 학생들은 운동장에서 캔 돌이 가득 담긴 주머니를 들고 한 줄로 선다.

이 반 아이들은 위험한 성격 조합을 가지고 있다. 질투가 많고, 똑똑하고, 눈썰미가 좋으며, 세기를 잘한다. 각 아이는 자기 앞에 있는 모든 아이가 돌을 몇 개 가지고 있는지 안다. 즉, 맨 앞에 선 아이는 자기 돌 개수를 알고, 두 번째 아이는 자기와 맨 앞 아이의 돌 개수를 알며, 세 번째 학생은 줄의 처음 세 학생의 돌 개수를 안다. 이런 식으로 계속된다.

자기보다 앞에 있는 아이 중 자기와 돌 개수가 같거나 더 많은 아이가 있다는 것을 알게 되면, 그 아이는 울기 시작한다. 맨 앞에 선 아이는 반 친구들에게 성숙하고 의연한 본보기를 보여야 하므로 절대 울지 않는다.

프리즈 선생님이 학생들을 최적으로 배치한다면, 쉬는 시간이 끝난 뒤 우는 학생 수의 최솟값은 얼마인가?

첫 번째 줄에는 정수 $N$이 주어진다 ($1 \leq N \leq 10^5$. 예산 삭감으로 학급 규모가 커지고 있다). 다음 줄에는 $N$개의 정수가 공백으로 구분되어 주어지며, $i$번째 정수는 $i$번 아이가 가진 돌의 개수이다. 각 아이는 돌을 최소 $1$개, 최대 $10^9$개 가진다.

학생들을 최적으로 배치했을 때 우는 아이 수의 최솟값을 정수 하나로 출력한다.

첫 번째 예시에서 최적 배치는 $[1, 1, 1, 2, 2, 2]$이다. 이때 $1$부터 세어 $2, 3, 5, 6$번째 학생이 운다. 우는 아이가 더 적은 배치는 없다.

두 번째 예시에서는 모든 아이가 같은 수의 돌을 가지고 있으므로, 어떻게 배치하든 두 명의 아이가 운다.