프로그램 명: brainman(open)
제한시간: 1 초

[문제 요약] 수열이 주어질 때 인접한 두 수를 교환함으로 이 수열을 정렬 시킬수가 있다.

최초의 수열이 2 8 0 3 이라면 

Start with: 2 8 0 3 
swap (2 8) 8 2 0 3 
swap (2 0) 8 0 2 3 
swap (2 3) 8 0 3 2 
swap (8 0) 0 8 3 2 
swap (8 3) 0 3 8 2 
swap (8 2) 0 3 2 8 
swap (3 2) 0 2 3 8 
swap (3 8) 0 2 8 3 
swap (8 3) 0 2 3 8
9 번의 교환만에 이 수열을 정렬 시켰다.

그런데 다음과 같이 하면 3 번 만에 가능하다. 

Start with: 2 8 0 3 
swap (8 0) 2 0 8 3 
swap (2 0) 0 2 8 3 
swap (8 3) 0 2 3 8
문제는 주어지는 수열에서 인접한 두수의 교환으로 수열을 정렬시킬수 있는 최소 자리 바꿈 횟수를 구하는 것이다.

입력

첫 번째 수는 테스트 데이터의 수이다. 각 테스트 별 첫 수는 수열의 개수 N 이 주어진다.( 1 <= N <= 1000 ). 그리고 N 개의 수가 주어진다. 모든 수는 [-1000000, 1000000] 이다.

출력

출력은 다음의 답을 출력한다.

입출력 예

입력

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

출력

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

출처: TUD Programming Contest 2003, Darmstadt, Germany
[질/답] [제출 현황] [푼 후(1)]
[ 채 점 ] [홈으로]  [뒤 로]