Trouble Sort

Code Jam의 비밀 알고리즘 연구실에서는 정수 목록을 비내림차순으로 정렬하는, 현시대에서 가장 복잡한 문제 중 하나에 많은 시간을 쏟고 있다. 고전적인 버블 정렬 알고리즘을 면밀히 살펴보았고, 새로운 변형을 발표하게 되었다.

일반 버블 정렬의 기본 연산은 인접한 두 수를 살펴보고, 왼쪽 수가 오른쪽 수보다 크면 그 두 수를 뒤집는다. 이 알고리즘은 인접한 세 수를 한 묶음으로 살펴본다. 가장 왼쪽 수가 가장 오른쪽 수보다 크면 묶음 전체를 뒤집는다. 이 알고리즘은 '세 수 버블 정렬'이므로 Trouble Sort라고 부른다.

TroubleSort(L): // L은 0부터 시작하는 정수 리스트
  let done := false
  while not done:
    done = true
    for i := 0; i < len(L)-2; i++:
      if L[i] > L[i+2]:
        done = false
        L[i]부터 L[i+2]까지의 부분 리스트를 뒤집는다

예를 들어 L = 5 6 6 4 3일 때 Trouble Sort는 다음과 같이 진행된다.

첫 번째 패스: 5 6 6은 아무 작업도 하지 않아 5 6 6 4 3이 그대로다. 6 6 4는 6 > 4이므로 뒤집혀 5 4 6 6 3이 된다. 6 6 3은 6 > 3이므로 뒤집혀 5 4 3 6 6이 된다.

두 번째 패스: 5 4 3은 5 > 3이므로 뒤집혀 3 4 5 6 6이 된다. 이후 4 5 6과 5 6 6은 아무 작업도 하지 않는다.

세 번째 패스에서는 세 묶음을 모두 검사하지만 아무 작업도 하지 않으므로 알고리즘이 종료된다.

Hawaii에서 열리는 Special Interest Group in Sorting 학회에서 Trouble Sort를 발표할 예정이었지만, 인턴 한 명이 문제를 지적했다. Trouble Sort가 목록을 올바르게 정렬하지 못할 수도 있다는 것이다. 예를 들어 목록 8 9 7을 생각해 보자.

N개의 정수 목록이 주어졌을 때, Trouble Sort가 목록을 비내림차순으로 올바르게 정렬하는지 판단하라. 정렬하지 못한다면, 알고리즘이 끝난 뒤 처음으로 나타나는 정렬 오류의 인덱스(0부터 셈)를 구하라. 즉, 알고리즘이 끝난 뒤 바로 다음 값보다 큰 값이 처음 나타나는 위치다.

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 목록의 값 개수 $N$이 주어지고, 둘째 줄에는 목록의 값 $N$개 $V_i$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 테스트 케이스 번호(1부터 셈)이다. $y$는 Trouble Sort가 목록을 올바르게 정렬하면 OK이고, 그렇지 않으면 첫 정렬 오류의 인덱스(0부터 셈)이다.

$1 \le T \le 100$.

모든 $i$에 대해 $0 \le V_i \le 10^9$.

샘플 케이스 #1은 문제 설명의 첫 번째 예와 비슷하다. Trouble Sort가 이 목록을 올바르게 정렬하므로 답은 OK이다.

샘플 케이스 #2는 문제 설명의 두 번째 예다. Trouble Sort는 목록을 7 9 8로 남긴 채 종료하므로 올바르게 정렬하지 못한다. 목록에서 다음 값보다 큰 값이 처음 나타나는 것은 9이므로 첫 정렬 오류의 인덱스는 1이다.