2979 - Another Sorting Problem

Created by Yonny Mondelo Hernández
Added by ymondelo20 (2014-07-17)
Limits
Total Time: 60000 MS | Test Time: 2000 MS |Memory: 62 MB | Output: 64 MB | Size: 14 KB
Enabled languages
Available in

Description

A permutation of the integers between 1 and N is given. Initially, they are positioned in an arbitrary order, but you want to rearrange the numbers, leaving them in increasing order. To do so, you use the following procedure:
  • First, pick any number which is not in their corresponding position.
  • Then, move this number into its corresponding position.  Another number may be occupying this location, so you must also move this number to its correct position. Repeat this step while possible.
  • Finally, repeat from the first step while possible.

Once these steps finish, the sequence will be ordered. You wish to know the amount of affected numbers during this sorting procedure. A number is considered affected if their initial position is distinct to their final position.

A permutation of the integers between 1 and N is given. Initially, they are positioned in an arbitrary order, but you want to rearrange the numbers, leaving them in increasing order. To do so, you use the following procedure:
  • First, pick any number which is not in their corresponding position.
  • Then, move this number into its corresponding position.  Another number may be occupying this location, so you must also move this number to its correct position. Repeat this step while possible.
  • Finally, repeat from the first step while possible.

Once these steps finish, the sequence will be ordered. You wish to know the amount of affected numbers during this sorting procedure. A number is considered affected if their initial position is distinct to their final position.

A permutation of the integers between 1 and N is given. Initially, they are positioned in an arbitrary order, but you want to rearrange the numbers, leaving them in increasing order. To do so, you use the following procedure:
  • First, pick any number which is not in their corresponding position.
  • Then, move this number into its corresponding position.  Another number may be occupying this location, so you must also move this number to its correct position. Repeat this step while possible.
  • Finally, repeat from the first step while possible.

Once these steps finish, the sequence will be ordered. You wish to know the amount of affected numbers during this sorting procedure. A number is considered affected if their initial position is distinct to their final position.

Input specification

The first line contain a integer number T (1 <= T <= 100), the number of test cases. For each case:
  • The first line contains an integer number N (1 <= N <= 50), the number of integers in the sequence.
  • The second line contains N space-separated integer numbers, a permutation of the numbers between 1 and N.

The first line contain a integer number T (1 <= T <= 100), the number of test cases. For each case:
  • The first line contains an integer number N (1 <= N <= 50), the number of integers in the sequence.
  • The second line contains N space-separated integer numbers, a permutation of the numbers between 1 and N.

The first line contain a integer number T (1 <= T <= 100), the number of test cases. For each case:
  • The first line contains an integer number N (1 <= N <= 50), the number of integers in the sequence.
  • The second line contains N space-separated integer numbers, a permutation of the numbers between 1 and N.

Output specification

For each case, you must print a line with the amount of affected numbers during the described sorting procedure.
For each case, you must print a line with the amount of affected numbers during the described sorting procedure.
The first line contain a integer number T (1 <= T <= 100), the number of test cases. For each case:
  • The first line contains an integer number N (1 <= N <= 50), the number of integers in the sequence.
  • The second line contains N space-separated integer numbers, a permutation of the numbers between 1 and N.

Sample input

3
1
1
5
2 3 1 5 4
9
3 2 1 5 4 7 8 6 9

Sample output

0
5
7

Hint(s)