22975번 - 도시 계획 서브태스크

현욱이 살고 있는 도시에는 $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 $).

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

$ 1 \le N \le 8 $

$ 1 \le N \le 400 $

추가 제한 없음