버블 정렬

버블 정렬은 배열에서 서로 이웃한 두 값을 비교하고, 앞의 값이 뒤의 값보다 크면 두 값을 바꾸는 과정을 반복하는 정렬 방법이다. 서로 다른 정수 N개가 정수 배열 A[0], A[1], ..., A[N-1]에 저장되어 있다. 배열 A를 오름차순으로 정렬하기 위해 태국이는 다음 코드를 작성했다.

for (i=0; i<N; i++) {    flag = 0;    for (j=0; j<N-1; j++) {        if (A[j] > A[j+1]) {            flag = 1;            temp = A[j];            A[j] = A[j+1];            A[j+1] = temp;        }    }}

그러나 입력 배열에 따라서는 변수 i가 모든 반복을 수행하기 전에 이미 정렬이 끝날 수 있다. 그래서 도현이는 한 번의 바깥쪽 반복에서 교환이 한 번도 일어나지 않으면 정렬이 끝났다고 판단하도록 코드를 개선했다.

for (i=0; i<N; i++) {    flag = 0;    for (j=0; j<N-1; j++) {        if (A[j] > A[j+1]) {            flag = 1;            temp = A[j];            A[j] = A[j+1];            A[j+1] = temp;        }    }    if (flag == 0) {        break;    }}

주어진 배열 A를 위의 개선된 코드로 정렬했을 때, 바깥쪽 for 문을 빠져나오는 순간 변수 i에 저장된 값을 구하시오.

첫째 줄에 정수 N(1 <= N <= 500,000)이 주어진다.

둘째 줄에 배열 A를 이루는 N개의 정수가 공백으로 구분되어 순서대로 주어진다. 주어지는 정수는 모두 서로 다르며, 각 정수의 절댓값은 2,147,483,647을 넘지 않는다.

정렬이 완료되어 바깥쪽 for 문을 빠져나오는 순간 변수 i에 저장된 값을 출력한다.