E. 另一种折叠纸条
每次测试的时间限制：2 秒
每次测试的内存限制：256 兆字节

对于一个长度为 $m$ 的数组 $b$，定义 $f(b)$ 如下：

考虑一个 $1 \times m$ 的纸条，初始时所有格子的暗度为 $0$。
你想把它变成第 $i$ 个位置的暗度为 $b_i$ 的纸条。
你可以进行如下操作，每次操作包含两步：

1. 在任意两个格子之间的线处折叠纸条。你可以折叠任意多次，也可以不折叠。
2. 选择一个位置滴下黑色染料。染料从顶部渗透到底部，使其路径上的所有格子的暗度增加 $1$。滴完染料后，你将纸条展开。

设 $f(b)$ 为达到目标配置所需的最少操作次数。可以证明，目标总是可以在有限次操作内实现。

现在给你一个长度为 $n$ 的数组 $a$。计算

$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(a_l a_{l+1} \dots a_r) $$

并对 $998244353$ 取模。

输入
每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。
接下来每个测试用例的描述如下：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组 $a$ 的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）——数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出一个整数 —— 所需的和模 $998244353$ 的结果。

示例
输入：

4
3
0 1 0
6
1 0 0 1 2 1
5
2 1 2 4 3
12
76 55 12 32 11 45 9 63 88 83 32 6

输出：

4
28
47
7001

注意
在第一个测试用例中：

• $f(a_1) = f(0) = 0$
• $f(a_1 a_2) = f(01) = 1$
• $f(a_1 a_2 a_3) = f(010) = 1$
• $f(a_2) = f(1) = 1$
• $f(a_2 a_3) = f(10) = 1$
• $f(a_3) = f(0) = 0$

总和为 $0+1+1+1+1+0 = 4$。

在第二个测试用例中，$f(a_1 a_2 a_3 a_4 a_5 a_6) = 2$。这里给出了一种可能的操作序列（省略）。