题目描述 小 Z 有一个长度为 ? n 的序列 ?

{ ? 1 , ? 2 , ⋯   , ? ? } A={a 1 ​ ,a 2 ​ ,⋯,a n ​ }。

小 Y 给出了一个定义：对于一个一个长度为 ? n 的序列 ? B 是好的，当且仅当对于 1 ≤ ? < ? 1≤i<n，都有 ? ? ≠ ? ? + 1 b i ​

 =b i+1 ​ 。

问，有多少个长度为 ? n 的好的正整数序列 ? B，满足对于 1 ≤ ? ≤ ? 1≤i≤n 都有 1 ≤ ? ? ≤ ? ? 1≤b i ​ ≤a i ​ ，答案对 998244353 998244353 取模。

输入格式 第一行包含一个正整数 ? n，表示序列 ? A 的长度。

第二行输入 ? n 个整数 ? 1 , ? 2 , ⋯   , ? ? a 1 ​ ,a 2 ​ ,⋯,a n ​ 。

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

样例 输入数据 1 3 2 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 说明/提示 样例 1 解释 满足要求的序列有 { 1 , 2 , 1 } {1,2,1}， { 2 , 1 , 2 } {2,1,2}。 数据范围 对于所有测评数据， 1 ≤ ? ≤ 1 0 6 , 1 ≤ ? ? ≤ 1 0 9 1≤n≤10 6 ,1≤a i ​ ≤10 9 。