회전

1 이상 $N$ 이하의 서로 다른 정수로 이루어진 길이 $N$의 정수열 $P = (p_1, p_2, \dots, p_N)$이 있다. 이 정수열의 연속한 부분열을 골라 회전이라는 연산을 할 수 있다. 더 정확히는, 다음 두 종류의 연산을 임의의 순서로 임의 횟수만큼 할 수 있다.

• $1 \le b < e \le N$을 만족하는 두 정수 $b$, $e$를 고른다. 연속 부분열 $p_b, \dots, p_e$의 맨 앞 원소를 그 연속 부분열의 맨 뒤로 옮긴다. 즉 $p_b, p_{b+1}, p_{b+2}, \dots, p_{e-2}, p_{e-1}, p_e$를 각각 $p_{b+1}, p_{b+2}, p_{b+3}, \dots, p_{e-1}, p_e, p_b$로 바꾼다.
• $1 \le b < e \le N$을 만족하는 두 정수 $b$, $e$를 고른다. 연속 부분열 $p_b, \dots, p_e$의 맨 뒤 원소를 그 연속 부분열의 맨 앞으로 옮긴다. 즉 $p_b, p_{b+1}, p_{b+2}, \dots, p_{e-2}, p_{e-1}, p_e$를 각각 $p_e, p_b, p_{b+1}, \dots, p_{e-3}, p_{e-2}, p_{e-1}$로 바꾼다.

어느 연산이든 한 번에 고른 연속 부분열의 길이, 즉 $e-b+1$만큼의 비용이 든다.

이 연산들을 사용해 정수열 $P$의 원소를 오름차순으로 정렬하려고 한다. 즉 모든 $1 \le i \le N$에 대해 $p_i = i$가 되게 하려고 한다. 이를 위해 필요한 비용의 합의 최솟값을 구하시오.

입력은 50개 이하의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

N
p1 p2 … pN

첫째 줄에는 정수열의 길이 $N$ ($2 \le N \le 10^5$)이 주어진다. 둘째 줄에는 정수열 $P$의 각 원소 $p_i$ ($1 \le p_i \le N$)가 공백으로 구분되어 주어진다. $i \ne j$이면 $p_i \ne p_j$임이 보장된다.

입력의 끝은 0 하나로 이루어진 줄로 나타낸다.

각 데이터 세트에 대해, 정수열 $P$를 오름차순으로 정렬하는 데 필요한 비용의 합의 최솟값을 한 줄에 출력한다.