CF2249B Permutation Cuts

You are given an integer $ n $ and an array $ a $ of length $ n-1 $ . For a permutation $ ^{\text{∗}} $ $ p $ of length $ n $ , define $$$ v_i=\min\left(\max_{1\le j\le i}p_j, \max_{i+1\le j\le n}p_j\right), $$$ where $ 1\le i\le n-1 $ . In other words, cut the permutation between positions $ i $ and $ i+1 $ , take the maximum element on each side, and let $ v_i $ be the smaller of these two values. Your task is to count the number of permutations $ p $ of length $ n $ such that $ v_i=a_i $ for each $ 1\le i\le n-1 $ . Output the answer 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 one integer $ n $ ( $ 2\le n\le 10^6 $ ) — the length of $ p $ . The second line contains $ n-1 $ integers $ a_1,a_2,\ldots,a_{n-1} $ ( $ 1\le a_i\le n $ ) — the elements of $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, output one integer — the number of suitable permutations, modulo $ 998\,244\,353 $ .

In the first test case, both permutations $ [1,2] $ and $ [2,1] $ satisfy $ v_1=1 $ . In the second test case, the only suitable permutations are $ [2,1,3] $ and $ [3,1,2] $ . In the third test case, no suitable permutation exists.