AT_abc446_g [ABC446G] 221 Subsequence

For a sequence $ X = (X_1, \dots, X_n) $ of positive integers, we call $ X $ a **221 sequence** if and only if the length and value are equal for every (length, value) pair in its run-length encoding. More formally, a sequence satisfying the following condition is called a 221 sequence. - For any integer pair $ (l, r) $ satisfying $ 1 \leq l \leq r \leq n $ , if all three of the following conditions hold, then $ (r-l+1) = X_l $ . - $ l = 1 $ or ( $ l \geq 2 $ and $ X_{l-1} \neq X_l $ ) - $ r = n $ or ( $ r \leq n-1 $ and $ X_{r+1} \neq X_r $ ) - $ X_l = X_{l+1} = \dots = X_r $ For example, $ (2,2,3,3,3,1,2,2) $ is a 221 sequence, but $ (1,1) $ and $ (4,4,1,4,4) $ are not 221 sequences. You are given a sequence $ A = (A_1, \dots, A_N) $ of positive integers of length $ N $ . Find the number, modulo $ 998244353 $ , of non-empty (not necessarily contiguous) subsequences of $ A $ that are 221 sequences. Even if two subsequences are extracted from different positions, they are counted as one if they are equal as sequences.

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

Output the answer on one line.

### Sample Explanation 1 The 221 sequences that appear as non-empty subsequences of $ A $ are the following five: - $ (1) $ - $ (1,2,2) $ - $ (2,2) $ - $ (2,2,1) $ - $ (2,2,1,2,2) $ ### Sample Explanation 2 No 221 sequences appear as non-empty subsequences of $ A $ . ### Constraints - $ 1 \leq N \leq 500\,000 $ - $ 1 \leq A_i \leq N $ - All input values are integers.