버블 정렬과 moo

시간 제한2초메모리 제한512 MB

요약

이 버블 정렬 구현에서 배열이 정렬될 때까지 바깥쪽 루프가 몇 번 실행되는지 센다.

난이도: 보통10점 중 7점
유형: 정렬, 배열, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

소 베시는 목장 밖의 진로도 생각하며 여러 온라인 코딩 사이트에서 알고리즘을 배우기 시작했다.

지금까지 베시가 가장 좋아하는 알고리즘은 버블 정렬이다. 길이가 $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"를 출력하는 일만 한다. 그런데도 베시는 코드 곳곳에 이 명령을 넣어 둔다.

배열이 주어지면 베시의 코드가 "moo"를 몇 번 출력하는지 구하라.

입력

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

출력

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

예제3

예제 1
입력
```
5
1
5
3
8
2
```
예상 출력
```
4
```
예제 2
입력
```
1
42
```
예상 출력
```
1
```
예제 3
입력
```
6
1
2
3
4
5
6
```
예상 출력
```
1
```