버블 정렬

시간 제한

2초

메모리 제한

128 MB

문제

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

cpp

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;    }}

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

출력

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