Problem G
Greatest Permutation

A permutation with $n$ elements is a rearrangement of the first $n$ positive integers. For example, if $n=3$, there are $6$ permutations: $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$ and $(3,2,1)$. A great permutation is a permutation with $n$ elements with the form $i,i+1,i+2,\dots ,n,1,2,\dots ,i-1$. In other words, a great permutation can be obtained by moving a prefix of $1,2,\dots ,n$ to its right. Please note that $1,2,\dots ,n$ is also a great permutation.

For a permutation, let’s define its weight as the minimum number of times you need to swap two consecutive elements, so that the permutation becomes a great permutation.

For example, the weight of $3,2,1,4$ is $2$, because you can make it a great permutation after a minimum of two swaps:

• Swap the $1$st and $2$nd element: $2,3,1,4$,

• Swap the $3$rd and $4$th element: $2,3,4,1$.

You are given a sequence representing a permutation with some missing elements. You need to calculate the minimum weight among all permutations which can be obtained by replacing missing elements with certain values. For example, given the sequence $2,3,0,0$, where $0$s denote missing elements, two possible permutations are $2,3,1,4$ with weight $1$ and $2,3,4,1$ with weight $0$. So the minimum weight is $0$.

Input

The first line of the input contains a single integer $t$ — the number of test cases. $t$ test cases follow, each test case is described as below:

• The first line contains a single integer $n$ $(1\le n\le {10}^6)$ — the number of elements of the given permutation.

• The second line contains $n$ space-separated integers $a_1,a_2,\dots ,a_n$ $(0\le a_i\le n)$. It is guaranteed that you can get at least one valid permutation after changing all $0$s to other values.

The sum of $n$ in all test cases does not exceed ${10}^6$.

Output

For each test case, print the result in a single line.

2
4
3 2 1 4
4
2 3 0 0

2
0