정렬이 서툰 소

농장 밖의 진로를 고민하던 소 베시가 여러 온라인 코딩 사이트에서 알고리즘을 배우기 시작했다.

지금까지 베시가 가장 좋아하는 알고리즘은 버블 정렬이다. 길이가 $N$인 배열 $A$를 정렬하는 첫 구현을 베시는 소 언어로 이렇게 작성했다.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

소 언어에서 moo 명령은 moo를 출력하기만 한다. 베시는 코드 여기저기에 이 명령을 꼭 넣는다.

여러 배열에 코드를 돌려 본 베시는 한 가지를 알아냈다. 큰 원소는 배열 끝으로 아주 빠르게 밀려가지만, 작은 원소가 앞쪽으로 거품처럼 떠오르는 데에는 오래 걸린다. 베시는 알고리즘 이름이 여기서 왔다고 짐작한다. 이 문제를 줄이려고 베시는 주 반복문을 고쳤다. 한 번의 반복에서 앞에서 뒤로 훑은 다음 뒤에서 앞으로 훑으면, 큰 원소와 작은 원소가 모두 한 번의 반복에서 먼 거리를 이동할 기회를 얻는다. 고친 코드는 다음과 같다.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

배열이 주어질 때, 베시가 고친 코드가 moo를 몇 번 출력하는지 예측하라.

첫째 줄에 $N$이 주어진다 ($1 \leq N \leq 100000$). 다음 $N$개 줄에는 배열의 원소 $A_0$부터 $A_{N-1}$까지가 한 줄에 하나씩 주어진다. 각 원소는 $0 \leq A_i \leq 10^9$인 정수이며, 서로 다르다는 보장은 없다.

moo가 출력되는 횟수를 출력한다.