버블 정렬

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

요약

배열이 주어졌을 때, N이 최대 50만인 상황에서 O(N^2) 버블 정렬을 직접 시뮬레이션하지 않고 교환이 멈추는 패스 번호를 구합니다.

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

문제

다음 C++ 코드와 같은 버블 정렬을 실행한다고 하자.

bool changed = false;
for (int i = 1; i <= N + 1; i++) {
    changed = false;
    for (int j = 1; j <= N - i; j++) {
        if (A[j] > A[j + 1]) {
            changed = true;
            swap(A[j], A[j + 1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

여기서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 A[N]까지 사용한다.

이 코드를 실행했을 때 출력되는 값을 구하라.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 500,000 이하인 자연수이다.

둘째 줄부터 N개의 줄에는 A[1], A[2], ..., A[N]이 한 줄에 하나씩 주어진다. 각 값은 0 이상 1,000,000 이하인 정수이다.

출력

코드가 출력하는 값을 출력한다.

예제2

예제 1
입력
```
5
10
1
5
2
3
```
예상 출력
```
3
```
예제 2
입력
```
5
1
3
5
7
9
```
예상 출력
```
1
```