Monotonic Renumeration

题意翻译

给出一个长为$n$的序列$a_1...a_n$，根据序列$a$构建一个单调的序列$b$，要求： 1. $b_1 = 0$ 2. 对于任何一组$i, j(1 \le i, j \le n)$ ,如果$a_i = a_j$,则$b_i=b_j$($a_i\neq a_j$时无限制) 3. 对于$i \in [1, n - 1]$,$b_{i+1} = b_{i}$或$b_{i+1} = b_{i}+1$ 例如，$a = [1,2,1,2,3]$时，$b$可以是$[0,0,0,0,0]$或$[0,0,0,0,1]$ 请计算$b$的数量，答案对$998244353$取模 $1 \le n \le 2 \cdot 10^5$, $1 \le a_i \le 10^9$

题目描述

You are given an array $ a $ consisting of $ n $ integers. Let's denote monotonic renumeration of array $ a $ as an array $ b $ consisting of $ n $ integers such that all of the following conditions are met: - $ b_1 = 0 $ ; - for every pair of indices $ i $ and $ j $ such that $ 1 \le i, j \le n $ , if $ a_i = a_j $ , then $ b_i = b_j $ (note that if $ a_i \ne a_j $ , it is still possible that $ b_i = b_j $ ); - for every index $ i \in [1, n - 1] $ either $ b_i = b_{i + 1} $ or $ b_i + 1 = b_{i + 1} $ . For example, if $ a = [1, 2, 1, 2, 3] $ , then two possible monotonic renumerations of $ a $ are $ b = [0, 0, 0, 0, 0] $ and $ b = [0, 0, 0, 0, 1] $ . Your task is to calculate the number of different monotonic renumerations of $ a $ . The answer may be large, so print it modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of elements in $ a $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ).

输出格式

Print one integer — the number of different monotonic renumerations of $ a $ , taken modulo $ 998244353 $ .

输入输出样例

输入样例 #1

5
1 2 1 2 3

输出样例 #1

2

输入样例 #2

2
100 1

输出样例 #2

2

输入样例 #3

4
1 3 3 7

输出样例 #3

4