CF2190E Median Permutation

For a permutation $ ^{\text{∗}} $ $ q $ of size $ m \ge 3 $ , define $ f(q) $ to be a sequence $ b $ of size $ m - 2 $ such that $ b_i = \operatorname{med}(q_i, q_{i + 1}, q_{i + 2}) $ for all $ 1 \le i \le m - 2 $ . Here, $ \operatorname{med}(x, y, z) $ denotes the second smallest element among $ \{x, y, z\} $ . You are given an array $ a $ of size $ n $ , where some elements may be $ 0 $ . It is guaranteed that $ a $ contains the values $ 1 $ and $ n $ (that is, there exist indices $ i, j $ such that $ a_i = 1 $ and $ a_j = n $ ). Find the number of permutations $ p $ of size $ n $ satisfying the following conditions: - $ p $ is consistent with $ a $ : for all $ 1 \le i \le n $ , if $ a_i \neq 0 $ , then $ p_i = a_i $ . - All elements of $ f(p) $ are distinct. Since the answer can be large, print it modulo $ 998\,244\,353 $ . $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the size of the array. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le n $ ). It is guaranteed that all non-zero elements of $ a $ are pairwise distinct. It is also guaranteed that $ a $ contains the values $ 1 $ and $ n $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, print a single integer — the number of permutations $ p $ satisfying the conditions, modulo $ 998\,244\,353 $ .

In the first example, the only permutation consistent with the input is $ p = [1, 3, 2] $ . We have $ f(p) = [2] $ , since $ \operatorname{med}(1, 3, 2) = 2 $ . The elements of $ f(p) $ are distinct, so this permutation is valid. The answer is $ 1 $ . In the second example, there are two permutations consistent with the input: $ p = [3, 5, 4, 1, 2] $ and $ p = [2, 5, 4, 1, 3] $ . - For $ p = [3, 5, 4, 1, 2] $ , $ f(p) = [4, 4, 2] $ . - For $ p = [2, 5, 4, 1, 3] $ , $ f(p) = [4, 4, 3] $ . In both cases, the value $ 4 $ appears twice in $ f(p) $ . Thus, there are no valid permutations, and the answer is $ 0 $ .