codeforces#P1761F2. Anti-median (Hard Version)
Anti-median (Hard Version)
Description
This is the hard version of the problem. The only difference between the two versions is the constraint on $n$. You can make hacks only if all versions of the problem are solved.
Let's call an array $a$ of odd length $2m+1$ (with $m \ge 1$) bad, if element $a_{m+1}$ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $m+1$-st position remains the same.
Let's call a permutation $p$ of integers from $1$ to $n$ anti-median, if every its subarray of odd length $\ge 3$ is not bad.
You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo $10^9+7$.
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $n$ $(2 \le n \le 10^6)$ — the length of the permutation.
The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, or $p_i = -1$) — the elements of the permutation. If $p_i \neq -1$, it's given, else it's unknown. It's guaranteed that if for some $i \neq j$ holds $p_i \neq -1, p_j \neq -1$, then $p_i \neq p_j$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
For each test case, output a single integer — the number of ways to set unknown values to obtain an anti-median permutation, modulo $10^9+7$.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $n$ $(2 \le n \le 10^6)$ — the length of the permutation.
The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, or $p_i = -1$) — the elements of the permutation. If $p_i \neq -1$, it's given, else it's unknown. It's guaranteed that if for some $i \neq j$ holds $p_i \neq -1, p_j \neq -1$, then $p_i \neq p_j$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
Output
For each test case, output a single integer — the number of ways to set unknown values to obtain an anti-median permutation, modulo $10^9+7$.
5
2
-1 -1
3
-1 -1 -1
4
1 2 3 4
6
-1 -1 3 4 -1 -1
8
-1 -1 -1 -1 -1 -1 -1 -1
2
4
0
1
316
Note
In the first test case, both $[1, 2]$ and $[2, 1]$ are anti-median.
In the second test case, permutations $[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$ are anti-median. The remaining two permutations, $[1, 2, 3]$, $[3, 2, 1]$, are bad arrays on their own, as their median, $2$, is in their middle.
In the third test case, $[1, 2, 3, 4]$ isn't anti-median, as it contains bad subarray $[1, 2, 3]$.
In the fourth test case, the only anti-median array you can get is $[5, 6, 3, 4, 1, 2]$.