题目描述

小 S 摆烂了。

小 S 有一个长度为 $n$ 的序列 $A$。他用下面的方式生成序列 $B$（同样长度）：

• 如果 $A_i < 0$，则$$B_i = - 2^{-A_i}$$
• 否则（即 $A_i \ge 0$），$$B_i = 2^{A_i}$$

也就是说，正的（或 $0$）的数会变成 $2$ 的正指数次幂，负的数会变成负的、大小是 $2$ 的对应正指数次幂。

你需要求出序列 $B$ 的最大子区间和（最大子段和，允许子区间为空），并输出这个最大值对 $998244353$ 取模的结果。

“可以为空”表示如果所有非空子区间的和都是负数，那么可以选择空区间，空区间和视为 $0$。

---

输入格式

第一行一个自然数 $n$。

第二行包含 $n$ 个整数 $A_i$。

---

输出格式

输出一行一个整数，表示答案。由于答案可能非常大，只需要输出答案对 $998244353$ 取模的结果。

---

样例

样例 1 输入

6
1 2 -2 1 3 -1

样例 1 输出

12

样例 1 解释

先把 $A$ 变成 $B$：

• $A_1=1 \ge 0 \Rightarrow B_1 = 2^{1} = 2$
• $A_2=2 \ge 0 \Rightarrow B_2 = 2^{2} = 4$
• $A_3=-2 < 0 \Rightarrow B_3 = -2^{-(-2)} = -2^{2} = -4$
• $A_4=1 \ge 0 \Rightarrow B_4 = 2^{1} = 2$
• $A_5=3 \ge 0 \Rightarrow B_5 = 2^{3} = 8$
• $A_6=-1 < 0 \Rightarrow B_6 = -2^{-(-1)} = -2^{1} = -2$

得到

$$B = [2, 4, -4, 2, 8, -2].$$

所有连续子区间中，区间 $[1,5]$（即 $B_1$ 到 $B_5$）的区间和最大：

$$2 + 4 - 4 + 2 + 8 = 12.$$

因此答案是 $12$，输出 $12 \bmod 998244353 = 12$。

---

样例 2 输入

见下发文件 pre_classic2.in。

样例 2 输出

见下发文件 pre_classic2.out。

本组数据满足子任务 1 的限制。

---

样例 3 输入

见下发文件 pre_classic3.in。

样例 3 输出

见下发文件 pre_classic3.out。

本组数据满足子任务 3 的限制。

---

样例 4 输入

见下发文件 pre_classic4.in。

样例 4 输出

见下发文件 pre_classic4.out。

本组数据满足子任务 5 的限制。

---

样例 5 输入

见下发文件 pre_classic5.in。

样例 5 输出

见下发文件 pre_classic5.out。

本组数据满足子任务 6 的限制。

---

数据范围与提示

本题按子任务评测（不考察多测清空）。

子任务编号	$n$	$\lvert A_i \rvert$	特殊性质	分值
1	$\le 2000$	$\le 10$	无	3
2	$\le 2\times 10^5$			12
3	$\le 2000$			10
4	$\le 2\times 10^5$	$\le 10^9$	A	20
5	$\le 2000$		无	25
6	$\le 2\times 10^5$			30

特殊性质 A： $A_i$ 在题目给定的范围内等概率随机生成，且数据有恰好三组。

---

对于 $100$ 的数据，满足：

• $1 \le n \le 2 \times 10^5$
• $1 \le |A_i| \le 10^9$