오르락내리락

서로 다른 정수로 이루어진 수열 $A = [A_{1}, A_{2}, ..., A_{N}]$이 주어지며, 이를 오르락내리락 수열(어떤 인덱스 m에 대해 $A_{1}$ < $A_{2}$ < ... < $A_{m}$ > $A_{m+1}$ > ... > $A_{N}$를 만족하며, m은 1 이상 N 이하인 수열)로 재배열하려 한다.

한 번에 수열에서 서로 인접한 두 원소를 맞바꾸는 방식으로 재배열한다. 예상할 수 있듯이, 오르락내리락 수열을 만드는 데 필요한 이러한 교환의 최소 횟수에 특히 관심이 있다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $A_{i}$ ≤ $10^{9}$ $A_{i}$는 서로 쌍마다 다르다.

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 10.

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 하나의 정수 N이 포함된 한 줄로 시작한다. 다음 줄에는 N개의 서로 다른 정수 $A_{1}$, ..., $A_{N}$가 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 A를 오르락내리락 수열로 재배열하는 데 필요한 최소 교환 횟수이다.

첫 번째 경우에는 수열이 이미 원하는 형태이므로(m=N=3) 교환이 필요하지 않다.

두 번째 경우에는 3와 7를 맞바꾸면 오르락내리락 수열이 된다(m=3).