혼합된 정렬

학교를 벗어나 장기적인 진로를 고려하고 있는 수현은 다양한 온라인 코딩 웹사이트에서 알고리즘을 배우기 시작했습니다. 그녀가 가장 좋아하는 두 가지 알고리즘은 '버블 정렬'과 '퀵소트'입니다. 하지만 수현는 불행히도 두 알고리즘을 쉽게 혼동하여 그 둘의 이상한 혼합 버전을 구현하게 됩니다!

배열 $A$에서 원소들 $i$와 $i+1$ 사이의 위치를 '분리 지점'이라고 부르겠습니다. 만약 배열 $A[...i]$의 최대값이 $A[i+1 \ldots]$의 최소값보다 크지 않다면, 이는 곧 '분리 지점'이 됩니다. 수현은 퀵소트가 배열을 재정렬하여 분리 지점을 만들고 두 개의 구역 $A[...i]$와 $A[i+1 \ldots]$을 재귀적으로 정렬한다는 것을 기억합니다. 그러나 그녀는 배열에서 모든 분리 지점들을 선형 시간 내에 결정할 수 있다는 사실을 정확히 인지하고 있지만, 퀵소트가 배열을 어떻게 빠르게 분리 지점을 만들기 위해 재정렬하는지 까먹어버렸습니다! 이는 정렬 알고리즘의 역사에서 가장 악명 높은 실수가 될 수도 있는데, 그것은 바로 이 작업을 위해 버블 소트를 사용하려는 불운한 결정을 내리게 되었기 때문입니다.

다음은 수현이 배열 $A$를 정렬하기 위해 처음으로 구현한 구현 방법의 개요입니다. 그녀는 먼저 버블 소트를 한 번 실행하는 간단한 함수를 작성합니다:

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

그녀의 퀵(ish) 소트 함수에 대한 재귀적인 코드는 다음과 같이 구조화되어 있습니다:

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 \leq N \leq 100,000$)이 주어집니다. 다음 $N$개의 줄에는 $A[0] \ldots A[N-1]$를 설명하는데, 각 값은 $0 \ldots 10^9$ 범위의 정수입니다. 입력 원소들이 모두 다른 것을 보장할 수 없습니다.

work_counter의 최종 값을 출력하세요.