로켓

화성인들이 새로운 우주 로켓을 만들고 있다. 로켓은 한 줄로 늘어선 $N$개의 모듈로 이루어지며, 앞에서부터 $1 \ldots N$까지 순서대로 번호가 붙어 있다. 모듈 $i$에는 $A_i$리터의 연료가 들어가며, 모든 모듈의 용량은 서로 다르다.

모듈은 $K$개의 단계로 묶어야 한다. 각 단계는 연속된 모듈 한 개 이상으로 이루어지고, 모든 모듈은 정확히 한 단계에만 속한다. 즉, 배열 $A$를 비어 있지 않은 연속 구간 $K$개로 나눠야 한다.

마지막 순간에 로켓이 가장 빨리 난다는 사실이 밝혀졌다. 각 단계 안에서 모듈이 용량의 오름차순으로 정렬되어 있을 때다. 모듈은 크고 무거워서 인접한 두 모듈을 맞바꾸는 데 한 시간이 걸리고, 서로 이웃하지 않은 모듈끼리는 맞바꿀 수 없다.

각 단계의 모듈이 용량 오름차순이 되도록 $K$개의 단계로 나눌 수 있게 하는 최소 교환 횟수를 구하는 프로그램을 작성하라.

첫 줄에는 모듈의 개수 $N$과 로켓 단계의 개수 $K$가 공백으로 구분되어 주어진다($1 \le K \le N \le 2000$).

둘째 줄에는 번호 순서대로 모듈의 용량 $A_i$가 공백으로 구분되어 $N$개 주어진다($1 \le A_i \le 10^9$). 모든 $A_i$는 서로 다르다.

모듈을 재배열하는 데 드는 최소 시간을 정수 하나로 출력한다. 시간 단위는 시간이다.