주어진 배열의 마지막 $i$개의 원소가 정렬되어 있다면 그 앞의 $N-i$개의 소들을 $N-i$번만에 정렬시킬 수 있습니다. 따라서 배열의 마지막부터 어디까지 정렬되어 있는지 체크하다가, 처음으로 정렬이 되어 있지 않은 소의 위치를 $O(N)$의 시간 복잡도로 찾으면 답을 구할 수 있습니다.