시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1612 264 194 23.487%

문제

영식이는 다음과 같은 버블 소트 프로그램을 C언어를 이용해서 작성했다.

int i,j,temp;
int change;
for (i=1; i<=N; i++){
    change = 0;
    for (j=1; j<=N-i; j++){
        if(A[j] > A[j+1]){
            change = 1;
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
    if (change == 0) {
        break;
    }
}
printf("%d\n",i);

위 소스에서 n은 배열의 크기이고, a는 수가 들어있는 배열이다. 수는 배열의 1번방부터 채운다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다.

출력

정답을 출력한다.

예제 입력

5
10
1
5
2
3

예제 출력

3

힌트

출처