엉터리 정렬

농장 밖의 진로를 고민하던 젖소 베시는 온라인 코딩 사이트에서 알고리즘을 공부하기 시작했다. 가장 좋아하는 알고리즘은 버블 정렬과 퀵 정렬인데, 둘을 자꾸 헷갈린 탓에 두 알고리즘을 어정쩡하게 섞은 정렬을 만들고 말았다.

배열 A에서 위치 $i$와 $i+1$ 사이를 분할점이라고 하자. 단, A[0..i]의 최댓값이 A[i+1..N-1]의 최솟값보다 크지 않을 때만 분할점이다. 퀵 정렬은 배열에 분할점이 생기도록 원소를 재배치한 다음 A[0..i]와 A[i+1..N-1] 양쪽을 재귀적으로 정렬한다. 베시는 여기까지는 기억하고, 배열의 모든 분할점을 선형 시간에 찾을 수 있다는 사실도 정확히 안다. 잊어버린 것은 분할점을 빠르게 만드는 재배치 방법이다. 그래서 베시는 그 자리에 버블 정렬 한 번 통과를 넣었다.

버블 정렬 한 번 통과는 이렇게 쓴다.

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

재귀 정렬 함수의 구조는 이렇다.

quickish_sort (A) {
   if length(A) = 1, return
   do { // main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A)
   divide A at all partition points; recursively quickish_sort each piece
}

베시는 자기 코드가 얼마나 빠른지 궁금하다. 주 반복문을 한 번 도는 비용이 그 배열의 길이에 비례한다고 보고, 반복문 안에서 전역 변수 work_counter에 그 길이를 더한다. 처음 배열이 주어질 때, quickish_sort를 실행한 뒤 work_counter의 최종 값을 구하라.

첫째 줄에 $N$이 주어진다 ($1 \le N \le 100000$). 다음 $N$개 줄에 A[0]부터 A[N-1]까지 한 줄에 하나씩 주어진다. 각 원소는 $0$ 이상 $10^9$ 이하의 정수다. 원소가 서로 다르다는 보장은 없다.

work_counter의 최종 값을 출력한다.

배열 20 2 3 4 9 8 7로 시작해 보자. 버블 정렬 한 번 통과가 카운터에 7을 더하고 2 | 3 | 4 | 9 8 7 | 20을 남긴다. 여기서 |는 분할점을 뜻한다. 길이가 1인 조각 2, 3, 4, 20은 비용이 들지 않는다. 조각 9 8 7은 주 반복문을 한 번 돌아(3) 8 7 | 9가 되고, 8 7을 마지막으로 한 번 더 돌면(2) 정렬이 끝난다. 카운터는 12에서 멈춘다.