Anti-median (Hard Version)

题意翻译

- 一个排列是好的，当且仅当对于所有正整数 $m$ 都满足所有长度为 $2m+1$ 的子串的**中位数**不在第 $m+1$ 个。 - 给定一个一些数被替换成 $-1$ 的排列，你需要将 $-1$ 填入所有可能的值后，统计好的排列数量。 - 答案对 $10^9+7$ 取模。 - 多测，$\sum n\leq 10^6$。

题目描述

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

输入输出样例

输入样例 #1

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

输出样例 #1

2
4
0
1
316

说明

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

**题意翻译**

- 一个排列是好的，当且仅当对于所有正整数 $ m $ 都满足所有长度为 $ 2m+1 $ 的子串的中位数不在第 $ m+1 $ 个。
- 给定一个一些数被替换成 $-1$ 的排列，你需要将 $-1$ 填入所有可能的值后，统计好的排列数量。
- 答案对 $ 10^9+7 $ 取模。
- 多测，$ \sum n \leq 10^6 $。

**题目描述**

这是问题的困难版本。两个版本之间的唯一区别是对 $ n $ 的限制。只有当问题的所有版本都被解决时，你才能进行 hack。

我们将长度为奇数 $ 2m+1 $ （其中 $ m \ge 1 $ ）的数组 $ a $ 称为坏的，如果元素 $ a_{m+1} $ 等于该数组的中位数。换句话说，如果对该数组进行排序后，第 $ m+1 $ 个位置的元素保持不变，则该数组是坏的。

我们将从 $ 1 $ 到 $ n $ 的整数的排列 $ p $ 称为反中位数，如果其每个长度大于等于 $ 3 $ 的奇数长度的子数组都不是坏的。

你已经得到了排列中某些元素的值。找出设置未知值以获得反中位数排列的方法数。由于这个数字可能非常大，因此求模 $ 10^9+7 $ 下的结果。

**输入输出格式**

**输入格式**

第一行包含一个整数 $ 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 $ 。

**输出格式**

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

**输入输出样例**

**输入样例 #1**
```
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
```

**输出样例 #1**
```
2
4
0
1
316
```

**说明**

在第一个测试用例中，两个排列 $ [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] $ 。**题意翻译** - 一个排列是好的，当且仅当对于所有正整数 $ m $ 都满足所有长度为 $ 2m+1 $ 的子串的中位数不在第 $ m+1 $ 个。 - 给定一个一些数被替换成 $-1$ 的排列，你需要将 $-1$ 填入所有可能的值后，统计好的排列数量。 - 答案对 $ 10^9+7 $ 取模。 - 多测，$ \sum n \leq 10^6 $。 **题目描述** 这是问题的困难版本。两个版本之间的唯一区别是对 $ n $ 的限制。只有当问题的所有版本都被解决时，你才能进行 hack。 我们将长度为奇数 $ 2m+1 $ （其中 $ m \ge 1 $ ）的数组 $ a $ 称为坏的，如果元素 $ a_{m+1} $ 等于该数组的中位数。换句话说，如果对该数组进行排序后，第 $ m+1 $ 个位置的元素保持不变，则该数组是坏的。 我们将从 $ 1 $ 到 $ n $ 的整数的排列 $ p $ 称为反中位数，如果其每个长度大于等于 $ 3 $ 的奇数长度的子数组都不是坏的。 你已经得到了排列中某些元素的值。找出设置未知值以获得反中位数排列的方法数。由于这个数字可能非常大，因此求模 $ 10^9+7 $ 下的结果。 **输入输出格式** **输入格式** 第一行包含一个整数 $ 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 $ 。 **输出格式** 对于每个测试用例，输出一个整数——设置未知值以获得反中位数排列的方法数，模 $ 10^9+7 $ 。 **输入输出样例** **输入样例 #1** ``` 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 ``` **输出样例 #1** ``` 2 4 0 1 316 ``` **说明** 在第一个测试用例中，两个排列 $ [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] $ 。