CF1761F2.Anti-median (Hard Version)

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$.

这是该问题的困难版本。两个版本之间的唯一区别在于对 $n$ 的约束条件。只有当该问题的所有版本均被解决时，才允许进行 hack。

我们称一个长度为奇数 $2m+1$（其中 $m \ge 1$）的数组 $a$ 是“坏”的，如果其中第 $m+1$ 个元素 $a_{m+1}$ 等于该数组的中位数。换言之，若将该数组排序后，原位于第 $m+1$ 位的元素在排序后仍处于第 $m+1$ 位，则该数组是“坏”的。

我们称一个由整数 $1$ 到 $n$ 构成的排列 $p$ 是“反中位数”的，如果它的每一个长度 $\ge 3$ 的奇数长度子数组都不是“坏”的。

题目已给出该排列中部分位置的值。请计算将未知位置填上适当数值，使得最终得到一个反中位数排列的方案数。由于该数目可能非常大，请输出其对 $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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^6$）—— 排列的长度。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$，或 $p_i = -1$）—— 排列的元素。若 $p_i \neq -1$，则该值已给出；否则该位置未知。保证：对任意 $i \neq j$，若 $p_i \neq -1$ 且 $p_j \neq -1$，则必有 $p_i \neq p_j$。

保证所有测试用例的 $n$ 值之和不超过 $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$.

对于每个测试用例，输出一个整数——即设定未知值以得到反中位数排列的方法数，对 $10^9+7$ 取模。

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]$.

在第一个测试用例中，$[1, 2]$ 和 $[2, 1]$ 均为反中位数排列。

在第二个测试用例中，排列 $[1, 3, 2]$、$[2, 1, 3]$、$[2, 3, 1]$、$[3, 1, 2]$ 均为反中位数排列。其余两个排列 $[1, 2, 3]$ 和 $[3, 2, 1]$ 本身即为坏数组，因为它们的中位数 $2$ 位于中间位置。

在第三个测试用例中，$[1, 2, 3, 4]$ 不是反中位数排列，因为它包含坏子数组 $[1, 2, 3]$。

在第四个测试用例中，唯一能得到的反中位数排列是 $[5, 6, 3, 4, 1, 2]$。