Trouble Sort

Deep in Code Jam's secret algorithm labs, we spend countless hours on one of the most complex problems of our time: sorting a list of integers into non-decreasing order. We have taken a careful look at the classic bubble sort algorithm and are pleased to announce a new variant.

The basic operation of standard bubble sort is to examine a pair of adjacent numbers and reverse that pair if the left number is larger than the right number. Our algorithm examines a group of three adjacent numbers. If the leftmost number is larger than the rightmost number, it reverses the entire group. Because the algorithm is a 'triplet bubble sort', we call it 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

For example, for L = 5 6 6 4 3, Trouble Sort proceeds as follows.

First pass: 5 6 6 does nothing, giving 5 6 6 4 3. Then 6 6 4 has 6 > 4, so it reverses to 5 4 6 6 3. Then 6 6 3 has 6 > 3, so it reverses to 5 4 3 6 6.

Second pass: 5 4 3 has 5 > 3, so it reverses to 3 4 5 6 6. Then 4 5 6 and 5 6 6 do nothing.

The third pass inspects the three triplets and does nothing, so the algorithm terminates.

We were looking forward to presenting Trouble Sort at the Special Interest Group in Sorting conference in Hawaii, but one of our interns has just pointed out a problem: Trouble Sort may not sort the list correctly. Consider the list 8 9 7, for example.

Given a list of $N$ integers, determine whether Trouble Sort will sort the list into non-decreasing order. If it will not, find the index (counting from 0) of the first sorting error after the algorithm has finished. That is, find the first value that is larger than the value directly after it when the algorithm is done.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of two lines: one line with an integer $N$, the number of values in the list, and one line with $N$ integers $V_i$, the list of values.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is OK if Trouble Sort correctly sorts the list. Otherwise, $y$ is the index (counting from 0) of the first sorting error.

$1 \le T \le 100$.

$0 \le V_i \le 10^9$ for all $i$.

Sample Case #1 is similar to the first one described in the problem statement. Trouble Sort correctly sorts this list, so the answer is OK.

Sample Case #2 is the second one described in the problem statement. Trouble Sort does not correctly sort this list, since it terminates with the list 7 9 8. The 9 is the first value in the list that is larger than the next value, so the index of the first sorting error is 1.