ICPC Asia Can Tho Regional Contest 2020

Start

2020-12-10 16:20 AKST

ICPC Asia Can Tho Regional Contest 2020

End

2020-12-10 21:20 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -190 days 1:10:08

Time elapsed

5:00:00

Time remaining

0:00:00

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, \ldots , n, 1, 2, \ldots , i-1$. In other words, a great permutation can be obtained by moving a prefix of $1, 2, \ldots , n$ to its right. Please note that $1, 2, \ldots , 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, \ldots , 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.

Sample Input 1 Sample Output 1
2
4
3 2 1 4
4
2 3 0 0
2
0