#MX95. 好的序列

好的序列

时间限制:2000ms

空间限制:1024MB

题目描述

给定长度为 nn 的正整数序列 aa​。

一个长度为 nn 的序列 bb 是好的,当且仅当对于 1≤i<n1 \leq i < n,都有 bi≠bi+1b_i ≠b_{i+1}。

求解有多少个长度为 nn 的好的正整数序列 bb,满足对于 1≤i≤n1 \leq i \leq n 都有 1≤bi≤ai1 \leq b_i \leq a_i,答案对 998244353998244353 取模。

输入格式

第一行包含 11 个正整数 nn​。

第二行给定长度为 nn 的正整数序列 aa。

输出格式

输出一行,输出 11 个整数,表示最终答案,答案对 998244353998244353 取模。

样例 1 输入

3
2 2 2

样例 1 输出

2

样例解释

满足要求的序列有 {1,2,1}\{1,2,1\},{2,1,2}\{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%20\% 的数据,1≤n≤500,1≤ai≤1031 \leq n \leq 500,1 \leq a_i \leq 10^3。

对于 40%40\% 的数据,1≤n≤5001 \leq n \leq 500​。

对于 60%60\% 的数据,1≤n≤50001 \leq n \leq 5000。

对于所有测评数据,1≤n≤106,1≤ai≤1091 \leq n \leq 10^6,1 \leq a_i \leq 10^9。