문제

흔히 점근 표기법 상 속도로 정렬 알고리즘을 비교합니다. 선택 정렬 같이 비교적 느린 정렬 알고리즘은 N개의 항목을 정렬하는 데 O(N²) 시간이 걸리는 반면, 합병 정렬 같이 비교를 기반으로 한 정렬 알고리즘은 몇몇 가정 아래  O(N log N) 시간까지 빨라질 수 있습니다. 비교를 기반으로 한 정렬이 아닌 버킷 정렬은 O(N) 시간이면 정렬을 마칩니다. 이는 버킷 정렬이 가능한 값의 범위가 N에 비해 작다고 가정하기 때문입니다. 일반적으로, 정렬 알고리즘의 속도는 정렬하는 데이터에 대한 가정에 따라 달라집니다. 

속도에도 불구하고 자주 무시 받는 정렬 알고리즘 중에 하나는 '세상에서 가장 빠른 정렬 알고리즘'입니다. 이 알고리즘은 O(1) 상수 시간에 정렬을 완료합니다. 물론 이 알고리즘은 입력이 빠른 접근이 가능한 메모리에 있는 배열이며 이미 정렬되었다고 가정합니다. 이 문제에서, '세상에서 가장 빠른 정렬 알고리즘'을 구현해봅시다.

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 정렬해야 하는 배열을 나타냅니다. 각 배열은 0 < N <= 100인 N으로 시작됩니다. 이후 정렬해야 하는 N개의 정수가, 감소하지 않는 순서로 들어옵니다. 정렬해야 하는 모든 정수는 0에서 100000 범위입니다. 마지막 테스트 케이스 뒤에는 하나의 0으로 구성된 줄이 들어옵니다.

출력

 각 테스트 케이스에 대해 (1부터 시작하는) 테스트 케이스의 번호에 이어 Sorting... done!을 출력합니다.