Migrated from Lutece 3028 爬山算法

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Bob Wang喜欢爬山。 他曾经花了整整一天的时间攀登峨眉山。一路上见识了石缝中的山涧，吊桥下的云海，云雾里的寺庙，还有金顶上的日出。当然峨眉山的猴子也很让人难忘，因为它们太烦人了。不仅如此，他还去过青城山、西岭雪山。很遗憾他还没去过四姑娘山。 正所谓拜水都江堰，问道青城山。爬山不仅仅可以磨练人的意志、锤炼人的品性，还可以在一路上欣赏美丽的风景，体验不同地方的风土人情。Bob Wang习惯把每次爬山的感受记录下来，时间长了，便写出了一本厚厚的书。 对山的记录是这本书的一大亮点。Bob Wang喜欢用一串数表示一座山。一座山由数座小山组成，每座小山可以用一个数表示它的高度。由于小山的高度各不相同，因此小山的排名也各不相同。比如用$\{5,2,8,10,4 \}$表示组成一座山的小山的高度，那么这座山可以表示为$\{3,1,4,5,2 \}$，记为这座山的原序列。可以看出，原序列是一个排列。 同时，Bob Wang还喜欢考察一座山的连续程度。一座山的连续程度如下定义：假设这座山表示为$\{p_1,p_2,...,p_n\}$，其连续程度为$\{a_1,a_2,...,a_n \}$，其中$a_i=\max\{r-l+1\},i\in [l,r]$，满足$p_j=p_{j-1}+1,\forall j\in (l,r]$或$p_j=p_{j-1}-1,\forall j\in (l,r]$。比如对于$\{3,1,4,5,2 \}$，它的连续序列为$\{1,1,2,2,1 \}$. Bob Wang最近在重温他的爬山记录，可是他惊奇地发现有一座山他只记录了连续序列，没有记录原序列。他想知道，对于这个连续序列，有多少种可能的山。两座山不同当且仅当它们的原序列不同。同时由于满足条件的山可能太多，因此结果需要对$998244353$取模。

Input

第一行一个整数$n$，表示这座山的小山数量。 第二行$n$个整数，表示连续序列$a$。

Output

一行一个整数，表示答案对$998244353$取模后的结果。

Samples

5
1 1 2 2 1

14

4
3 2 3 1

0

Constraints

$1\leq n\leq 10^5$, $1\leq a_i\leq n$.

Resources

2023 UESTC ICPC Training for Math