Minimum Swaps to Make Array Strictly Increasing

You are given an array of n distinct integers. Your task is to determine the minimum number of swaps required to rearrange the array such that it becomes strictly increasing. If it is impossible (due to duplicate elements) to form a strictly increasing sequence, print -1.

More formally, if you have an array A of size n, you should compute the minimum number of swaps required to convert A into a permutation of its sorted order. Recall that a strictly increasing sequence satisfies $$A_1 < A_2 < \cdots < A_n.$$

Note: Swapping any two elements counts as a single swap.

Example:

• For [1, 3, 5, 7, 9], the array is already strictly increasing, so the answer is 0.
• For [8, 2, 5, 6, 9, 3], it takes 3 swaps to arrange it in increasing order.
• For [4, 4, 4, 4] (with duplicates), it is impossible to form a strictly increasing sequence, so the answer is -1.

inputFormat

The first line contains an integer T representing the number of test cases.
For each test case, the first integer is n, the number of elements in the array, followed by n space-separated integers.

Example:

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

outputFormat

For each test case, output the minimum number of swaps required on a new line. If it is impossible to make the sequence strictly increasing (due to duplicate elements), output -1.

Example:

0
3
-1

## sample

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

0
3
-1

</p>