AT_awtf2026algo_b Window Records

You are given a sequence of positive integers of length $ N $ , $ A=(A_1,A_2,\ldots,A_N) $ . Find, modulo $ 998244353 $ , the number of sequences of positive integers of length $ N $ , $ x=(x_1,x_2,\ldots,x_N) $ , satisfying all of the following conditions. - $ x_i \leq A_i $ holds for all $ i $ . - There exists a permutation $ p=(p_1,p_2,\ldots,p_{2N-1}) $ of $ (1,2,\ldots,2N-1) $ satisfying the following condition. - For each $ i $ ( $ 1 \leq i \leq N $ ), consider the sequence of length $ N $ , $ (p_i,p_{i+1},\ldots,p_{i+N-1}) $ . There are exactly $ x_i $ different values that are "prefix max" of this sequence. More precisely, the number of indices $ j $ ( $ i \leq j \leq i+N-1 $ ) such that $ p_j = \max_{i \leq k \leq j} p_k $ is $ x_i $ .

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output the answer.

### Sample Explanation 1 For example, consider $ x=(2,1) $ . The condition is satisfied by $ p=(2,3,1) $ . There are four possible values of $ x $ : $ (1,1),(1,2),(2,1),(2,2) $ . ### Sample Explanation 3 For example, consider $ x=(3,1,3) $ . No choice of $ p $ satisfies the conditions. ### Constraints - $ 2 \leq N \leq 50 $ - $ 1 \leq A_i \leq N $ - All input values are integers.