버블 정렬

다음 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 이하인 정수이다.

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