F. Stack Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ stacks.Initially,there's an integer $$$a_i$$$ in the $$$i_{th}$$$ stack.

Your task is to sort it.Formally,the final arrangement should have $$$n$$$ stacks with each stack having precisely one number, such that they are in non-decreasing order.To do so, following move can be done any number of times:

  • Move a number from top of one stack to the top of some other stack.

Print the minimum number of moves required to sort the array, or $$$-1$$$ if it is not possible.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 2*10^5)$$$, denoting the number of test cases.

Each test case consists of two lines of input.

The first line contains an integer $$$n(1 \leq n \leq 2*10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1\leq a_i \leq n)$$$.

The sum of $$$n$$$ will not exceed $$$2*10^5$$$.

Output

For each test case,output on a new line — the minimum number of moves required to sort the array, or $$$-1$$$ if it is not possible.

Example
Input
6
3
2 3 1
3
2 2 1
1
1
2
2 1
4
2 1 4 3
6
2 3 1 3 1 2
Output
5
3
0
-1
6
8
Note

Test case $$$1$$$:

The minimum number of moves required is $$$5$$$.The following picture shows the specific process of the movement.