도로 정리

N개의 마을이 일렬로 늘어서 있다. 마을 i에서 마을 j로 가는 도로가 있으며, 각 도로는 고유한 우선순위를 가진다. 마을 왼쪽 끝에서 오른쪽 끝까지 이동할 때 도로들이 교차하지 않도록 일부 도로를 제거해야 한다.

N개의 도로가 주어졌을 때, 교차를 제거하기 위해 제거해야 할 최소 도로 수를 구하는 프로그램을 작성하시오.

도로의 우선순위는 1부터 N까지의 순열로 주어진다. i번째 마을에서 출발하는 도로의 우선순위가 주어진다. 두 도로가 교차한다는 것은 마을 a < b에서 출발하는 도로의 우선순위가 p_a > p_b인 경우를 의미한다.

입력

첫째 줄에 N이 주어진다. (1 <= N <= 100,000)

둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. i번째 정수는 마을 i에서 출발하는 도로의 우선순위이다.

출력

교차를 제거하기 위해 제거해야 할 최소 도로 수를 출력한다.

입출력 예시

입력 1

4
4 1 2 3

출력 1

1

입력 2

5
3 1 4 2 5

출력 2

2