트러블 소트

Code Jam의 비밀 알고리즘 연구소 깊숙한 곳에서, 우리는 우리 시대의 가장 복잡한 문제 중 하나인 정수 목록을 비감소 순서로 효율적으로 정렬하는 문제와 씨름하는 데 셀 수 없이 많은 시간을 바친다. 우리는 고전적인 버블 정렬 알고리즘을 주의 깊게 살펴보았으며, 새로운 변형을 발표하게 되어 기쁘다.

표준 버블 정렬 알고리즘의 기본 연산은 인접한 두 수로 이루어진 쌍을 살펴보고, 왼쪽 수가 오른쪽 수보다 크면 그 쌍을 뒤집는 것이다. 하지만 우리의 알고리즘은 인접한 세 수로 이루어진 그룹을 살펴보고, 가장 왼쪽 수가 가장 오른쪽 수보다 크면 그 그룹 전체를 뒤집는다. 우리의 알고리즘은 "세 쌍 버블 정렬"이므로, 줄여서 Trouble Sort라고 이름 붙였다.

TroubleSort(L): // L is a 0-indexed list of integers
    let done := false
    while not done:
      done = true
      for i := 0; i < len(L)-2; i++:
        if L[i] > L[i+2]:
          done = false
          reverse the sublist from L[i] to L[i+2], inclusive

예를 들어 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을 살펴보고 아무것도 하지 않는다: 3 4 5 6 6

• 5 6 6을 살펴보고 아무것도 하지 않는다: 3 4 5 6 6

• 이어지는 세 번째 패스에서는 세 개의 세 수 묶음을 살펴보고 아무것도 하지 않으므로, 알고리즘이 종료된다.

우리는 하와이에서 열리는 정렬 특별 관심 그룹 학회에서 Trouble Sort를 발표하기를 고대하고 있었지만, 방금 인턴 중 한 명이 문제를 지적했다. Trouble Sort가 목록을 올바르게 정렬하지 못할 수도 있다는 것이다! 예를 들어 목록 8 9 7을 생각해 보자.

추가 연구를 위해 여러분의 도움이 필요하다. N개의 정수로 이루어진 목록이 주어질 때, Trouble Sort가 목록을 비감소 순서로 성공적으로 정렬할지 판별한다. 정렬하지 못한다면, 알고리즘이 끝난 뒤 발생하는 첫 번째 정렬 오류의 인덱스(0부터 세기 시작함), 즉 알고리즘이 끝났을 때 바로 다음에 오는 값보다 큰 첫 번째 값의 인덱스를 구한다.

제한

1 ≤ T ≤ 100. 모든 i에 대해 0 ≤ $V_{i}$ ≤ $10^{9}$. 메모리 제한: 1GB.

테스트 세트 1 (공개)

3 ≤ N ≤ 100. 시간 제한(전체 테스트 세트): 10초.

테스트 세트 2 (비공개)

3 ≤ N ≤ $10^{5}$. 시간 제한(전체 테스트 세트): 20초.

특별 참고

이 문제의 테스트 세트 2에는 입력이 매우 많으므로, 버퍼링되지 않는 리더를 사용하면 입력을 읽는 속도가 느려질 수 있음에 유의한다. 또한 일부 언어는 기본 입력 버퍼 크기가 작다는 점을 명심한다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 한 줄에는 목록의 값 개수를 나타내는 정수 N이 주어지고, 다음 줄에는 값의 목록인 N개의 정수 $V_{i}$이 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작함)이고, y은 Trouble Sort가 목록을 올바르게 정렬한다면 OK이며, 그렇지 않다면 위에서 설명한 첫 번째 정렬 오류의 인덱스(0부터 세기 시작함)이다.

예제 케이스 #1은 문제 설명에서 처음 설명한 경우와 유사하다. Trouble Sort가 이 목록을 올바르게 정렬하므로 답은 OK이다.

예제 케이스 #2는 문제 설명에서 두 번째로 설명한 경우이다. Trouble Sort는 목록 7 9 8인 상태로 종료되므로 이 목록을 올바르게 정렬하지 못한다. 9은 목록에서 다음 값보다 큰 첫 번째 값이므로, 첫 번째 정렬 오류의 인덱스는 1이다.