크레인

BeczkoBit 공장은 바이트를 절이는 통(barrel)을 생산한다. 생산 라인은 완전히 자동화되어 있고, 병목은 창고다. 창고에서는 완성된 통들을 크기 순서대로, 즉 가장 작은 것부터 가장 큰 것까지 한 줄로 세워 두어야 한다. 모든 통의 크기는 서로 다르다.

정렬 작업은 여러 대의 크레인이 함께 수행한다. 각 크레인은 임의의 두 통의 위치를 서로 맞바꿀 수 있다. 크레인들은 병렬로 동작하며, 한 대의 크레인이 두 통을 맞바꾸는 데 $1$ 단위 시간이 걸린다. 한 단위 시간 동안 각 통은 최대 한 대의 크레인에 의해서만 옮겨질 수 있다. 즉, 같은 단위 시간에 이루어지는 두 번의 맞바꿈은 같은 통을 건드릴 수 없다.

통들을 크기 오름차순으로 정렬하는 데 필요한 최소 시간(단위 시간의 수)을 구하라.

첫째 줄에 통의 개수 $n$ ($1 \le n \le 100\,000$)이 주어진다. 둘째 줄에는 $\{1, 2, \ldots, n\}$의 서로 다른 정수 $n$개가 주어지며, 이는 창고에 놓인 순서대로 각 통의 크기를 나타낸다. 첫 번째 위치에 놓인 통은 첫 번째 수로, 마지막 위치에 놓인 통은 마지막 수로 표현된다.

통들을 크기 오름차순으로 정렬하는 데 필요한 최소 단위 시간의 수를 정수 하나로 한 줄에 출력한다.