题目描述

有 $n + 2$ 个整数 $a_0, a_1, .... a_n, a_{n+1}$，$a_0 = a_{n+1} = 0$ 。

你需要做确切地 $n$ 次操作，每次操作为以下形式：

选择一个整数 $x$ 满足 $a_x \not= 0$ ，使得 $a_x = 0$ ，令 $l = \max \limits_{i<x,a_ i=0}(i),r = \min \limits_{i>x,a_i=0}(i)$，

此次操作的花费为 $\max(a_l, a_{l+1}, . . . , a_{x−1}) + \max(a_{x+1}. . . , a_{r−1}, a_r)$ 牛币。

有多少不同的操作方式使得操作花费的牛币最少，两种操作不同当且仅当两种操作的操作序列不同。

答案对 $998244353$ 取模。

友情提示：本题正解复杂度很大，常数很小。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, . . . , a_n$。

输出格式

输出一行一个整数表示答案。

样例

5
2 2 2 1 1

40

88
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3

235381964

数据范围

对于全部数据，$1 \le a_i \le n$。