시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB39242482.759%

문제

You are given a sequence of distinct integers A = [A1, A2, ..., AN], and would like to rearrange it into an up and down sequence (one where A1 < A2 < ... < Am > Am+1 > ... > AN for some index m, with m between 1 and N inclusive).

The rearrangement is accomplished by swapping two adjacent elements of the sequence at a time. Predictably, you are particularly interested in the minimum number of such swaps needed to reach an up and down sequence.

입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing a single integer: N. The next line contains N distinct integers: A1, ..., AN.

Limits

  • 1 ≤ T ≤ 100.
  • 1 ≤ Ai ≤ 109
  • The Ai will be pairwise distinct.
  • 1 ≤ N ≤ 10.

출력

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of swaps required to rearrange A into an up and down sequence.

예제 입력 1

2
3
1 2 3
5
1 8 10 3 7

예제 출력 1

Case #1: 0
Case #2: 1

힌트

In the first case, the sequence is already in the desired form (with m=N=3) so no swaps are required.

In the second case, swapping 3 and 7 produces an up and down sequence (with m=3).

출처

Contest > Google > Code Jam > Google Code Jam 2014 > Round 2 B1번

채점 및 기타 정보

  • 예제는 채점하지 않는다.