好的序列

时空限制

时间限制 $2\text{s}$，内存限制 $1024\text{MB}$。

问题描述

给定长度为 $n$ 的正整数序列 $a$​。

一个长度为 $n$ 的序列 $b$ 是好的，当且仅当对于 $1 \leq i < n$，都有 $b_i ≠b_{i+1}$。

求解有多少个长度为 $n$ 的好的正整数序列 $b$，满足对于 $1 \leq i \leq n$ 都有 $1 \leq b_i \leq a_i$，答案对 $998244353$ 取模。

输入格式

第一行包含 $1$ 个正整数 $n$​。

第二行给定长度为 $n$ 的正整数序列 $a$。

输出格式

输出一行，输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入1

3
2 2 2

样例输出1

2

样例解释

满足要求的序列有 ${1,2,1}$，${2,1,2}$​。

样例输入2

10
2 3 4 5 9 8 7 1 2 3

样例输出2

28722

样例输入3

50
98 123 123 42 55 67 82 10 23 20 98 123 123 42 55 67 81 10 23 20 98 123 123 42 55 67 89 10 23 20 98 123 124 42 55 67 89 10 23 20 98 123 123 42 55 67 89 10 23 20 

样例输出3

149787148

评测数据规模

对于 $20$ 的数据，$1 \leq n \leq 500,1 \leq a_i \leq 10^3$。

对于 $40$ 的数据，$1 \leq n \leq 500$​。

对于 $60$ 的数据，$1 \leq n \leq 5000$。

对于所有测评数据，$1 \leq n \leq 10^6,1 \leq a_i \leq 10^9$。