돌탑 쌓기

문제

지윤이는 일렬로 놓인 돌 $N$개로 돌탑을 쌓으려고 한다. 돌의 무게는 모두 다르며, 각 돌에는 $1$부터 $N$까지의 번호가 하나씩 붙어 있다. 번호가 큰 돌일수록 더 무겁다.

지윤이는 왼쪽에 있는 돌부터 차례대로 다음 규칙에 따라 쌓는다.

1. 돌탑을 안정적으로 쌓기 위해서는 반드시 더 무거운 돌이 아래에 오도록 쌓아야 한다.
2. 아직 돌탑이 없거나 새 돌을 올릴 수 있는 돌탑이 없다면, 새 돌을 바닥에 놓아 높이가 $1$인 돌탑을 만든다.

모든 돌을 사용하면서 돌탑을 가능한 한 적게 만들려고 한다. 지윤이를 도와 돌탑 개수의 최솟값을 구해 주자.

입력

첫째 줄에 돌의 개수 $N$이 주어진다. $(1 \le N \le 1,000)$

둘째 줄에 돌을 쌓아야 하는 순서를 나타내는 $N$개의 정수 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어진다. $a_1, a_2, \ldots, a_N$은 $1$부터 $N$까지의 정수를 각각 정확히 한 번씩 포함한다.

출력

모든 돌을 주어진 순서대로 쌓았을 때 만들어지는 돌탑 개수의 최솟값을 출력한다.

예제 1

5
4 5 3 1 2

출력 1

2