Anti-median (Hard Version)
Contest: Pinely Round 1 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: combinatorics, dp, math

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

Input format:
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 format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
2
4
0
1
316

Editorial:
For this version, we have to analyze our dp a bit more.
Once again, how do anti-median permutations look? We consider the order of positions on the cycle, as in F1. We choose the position of $$$n$$$, and then, for $$$i$$$ from $$$n-1$$$ to $$$1$$$, we choose a position of number $$$i$$$ among two options: right to the right of the current segment or right to the left.
If we fill this way, do we always get an anti-median permutation? Not really. This way makes sure that elements at even positions are first increasing, then decreasing, and at odd positions, first decreasing, then increasing, but it doesn't make sure that the element at the even position is larger than its neighbors. How do we guarantee that? Well, some segments are just not allowed: those, which contain a prefix of odd positions, prefix of even positions, and the prefix of odd positions is larger (off by $$$\pm 1$$$, depending on the parity of $$$n$$$), and same for suffixes.
Another observation is that if we know where $$$x$$$ is, we only have to options for where can the segment of numbers from $$$x$$$ to $$$n$$$ be (to the right or to the left of $$$x$$$).
This reduces our problem to the following subproblem: we start from some segment and have to end in another segment by expanding the current segment by $$$1$$$ to the right or to the left without ever entering "bad segments." Turns out that we can solve this in $$$O(1)$$$! Indeed, represent expanding segment to the right by a move up in a coordinate plane and to the left by a move to the right. Then, we have to get from point $$$(0, 0)$$$ to some point $$$(a, b)$$$ by moving up or to the right without ever crossing some line of form $$$x = y + c$$$. This is a well-known counting problem.