줄을 벗어난 소

농부 존은 목장의 소를 한 마리도 빠짐없이 사진 한 장에 담으려고 한다.

사진이 보기 좋으려면 소들이 키가 작은 쪽부터 큰 쪽까지 한 줄로 서 있어야 한다. 존이 소를 그렇게 세우자마자, 늘 말썽을 부리는 베시가 줄에서 빠져나와 다른 자리에 끼어들었다.

존은 소 두 마리의 자리를 서로 바꿔서 줄을 다시 키 순서로 되돌리려고 한다. 줄을 키가 작은 쪽부터 큰 쪽 순서로 만드는 데 필요한 교환 횟수의 최솟값을 구하라. 자리를 바꾸는 두 소가 줄에서 이웃해 있을 필요는 없다.

첫째 줄에 소의 수 $N$이 주어진다 ($2 \le N \le 100$). 다음 $N$개 줄에는 베시가 자리를 옮긴 뒤 줄에 선 순서대로 각 소의 키가 한 줄에 하나씩 주어진다. 키는 $1$ 이상 $1\,000\,000$ 이하의 정수이고, 키가 같은 소가 여럿 있을 수 있다. 주어지는 줄은 키가 작은 순서로 정렬된 줄에서 소 한 마리가 빠져나와 다른 자리에 끼어든 결과다.

줄을 다시 키가 작은 쪽부터 큰 쪽 순서로 정렬하는 데 필요한 교환 횟수의 최솟값을 한 줄에 출력한다.

소 여섯 마리가 키 $2, 4, 7, 7, 9, 3$ 순서로 서 있다고 하자. 베시는 키가 $3$인 소이고, 존은 아래와 같이 세 번 교환해서 줄을 정렬한다.

2 4 7 7 9 3   (처음 줄)
2 4 7 7 3 9   (마지막 두 소를 교환)
2 4 3 7 7 9   (앞쪽의 7과 3을 교환)
2 3 4 7 7 9   (4와 3을 교환)