도시 계획

현욱이 사는 도시에는 $N$개의 빌딩이 있다. 빌딩은 전부 일렬로 세워져 있고, 첫 번째 빌딩부터 차례대로 $1$번부터 $N$번까지 번호가 붙어 있다. 이웃한 빌딩 사이의 간격은 모두 $1$로 같다. $i$번째 빌딩의 높이를 $H_i$라고 하면, 일렬로 선 빌딩을 정면에서 바라볼 때 $i$번째 빌딩은 $(i, 0)$과 $(i, H_i)$를 잇는 두께가 0인 선분으로 나타낼 수 있다.

임의의 $i$번째 빌딩과 $j$번째 빌딩에 대해서, $i$번째 빌딩의 옥상을 나타내는 점 $(i, H_i)$와 $j$번째 빌딩의 옥상을 나타내는 점 $(j, H_j)$를 잇는 선분이 다른 모든 빌딩과 만나지 않거나 빌딩의 끝점에서만 만나면 두 빌딩은 옥상에서 서로의 옥상을 볼 수 있다.

예를 들어 도시에 빌딩이 6개 있고 첫 번째 빌딩부터 순서대로 높이가 2, 3, 7, 6, 1, 4라고 하자. 이 경우 각 빌딩을 직선으로 나타내면 위와 같은 그림을 그릴 수 있다.

예시에서 첫 번째 빌딩의 옥상에서 네 번째 빌딩의 옥상을 보려고 하면, 위 그림의 왼쪽처럼 세 번째 빌딩에 가로막혀 서로 옥상을 볼 수 없다. 반면 세 번째 빌딩의 옥상에서 여섯 번째 빌딩의 옥상을 보려고 하면, 두 옥상을 이은 직선이 네 번째 빌딩의 옥상과 만나지만 끝점에서만 만나므로 서로의 옥상을 볼 수 있다.

현욱이 사는 도시의 시장은 어느 날 새로운 도시 계획을 발표했다. 이 계획에 따르면, 도시에 있는 모든 빌딩은 옥상에서 다른 모든 빌딩의 옥상을 볼 수 있어야 한다.

안타깝게도 이 도시 계획을 만족시키려면 일부 빌딩을 파괴해야 할 수도 있다. 시장은 파괴되는 빌딩의 개수를 최소화하려고 한다. 새로운 도시 계획을 위해 최소 몇 개의 빌딩을 파괴해야 하는지 계산해 보자.

첫 줄에 도시에 있는 빌딩의 개수 $N$($1 \le N \le 2000$)이 주어진다.

둘째 줄에는 도시에 있는 $N$개 빌딩의 높이 $H_i$가 맨 왼쪽 빌딩부터 순서대로 공백으로 구분되어 주어진다($1 \le H_i \le 10^9$).

첫째 줄에 조건을 만족하기 위해 파괴해야 하는 빌딩의 최소 개수를 출력한다.