3680: 牛牛和数组操作(第一轮02)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
有n + 2个整数a0, a1, . . . , an, an+1， a0 = an+1 = 0。你需要做确切地n次操作，每次 操作为以下形式：
选择一个整数x满足ax ≠ 0，使得ax = 0，令l = max (i), r = min (i)，此次操
i<x,a i =0 i>x,a i =0 作的花费为max(al, al+1+, . . . , ax−1) + max(ax+1. . . , ar−1, ar)牛币。
有多少不同的操作方式使得操作花费的牛币最少，两种操作不同当且仅当两种操 作的操作序列不同。
答案对998244353取模。
友情提示：本题正解复杂度很大，常数很小。
输入
第一行一个整数n。
第二行n个整数a1, a2, . . . , an 。
输出
输出一行一个整数表示答案。
样例输入 复制
5
2 2 2 1 1样例输出 复制
40提示
【样例 1 输入】
5
2 2 2 1 1
【样例 1 输出】
40
【样例 2 输入】
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
【样例 2 输出】
235381964
【数据范围】
