삽입 정렬(Insertion Sort)은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘입니다. 이 알고리즘은 뒤섞여 있는 카드를 순서대로 정리하는 방법과 같이, 카드를 한 장씩 뽑아 값에 따라 적절한 곳에 끼워 넣는 것을 반복하여 정리한는 것 처럼, 데이터 집합에서 요소를 하나식 뽑아 적절한 곳에 끼워 넣는 것을 반복하여 데이터 집합을 정렬하는 방법입니다.
입력데이터
6
6 4 2 3 1 5
1단계 : 4 6 2 3 1 5 -> 4를 1번째 자리에 삽입
2단계 : 2 4 6 3 1 5 -> 2를 1번째 자리에 삽입
3단계 : 2 3 4 6 1 5 -> 3을 2번째 자리에 삽입
4단계 : 1 2 3 4 6 5 -> 1을 1번째 자리에 삽입
5단계 : 1 2 3 4 5 6 -> 5를 5번째 자리에 삽입
위와 같이 정렬 과정을 거칠때, 정렬의 각 단계에서 정렬이 필요한 요소가 삽입될 자리를 출력하는 프로그램을 작성하시오.