E. Еще одна сгибающаяся лента
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$b$$$ длины $$$m$$$ определим $$$f(b)$$$ следующим образом.

Рассмотрим ленту размером $$$1 \times m$$$, где все ячейки изначально имеют темноту $$$0$$$. Вы хотите преобразовать ее в ленту, где цвет в $$$i$$$-й позиции имеет темноту $$$b_i$$$. Вы можете выполнять следующую операцию, состоящую из двух шагов:

  1. Согните бумагу по любой границе между двумя ячейками. Вы можете сгибать сколько угодно раз или вообще не сгибать.
  2. Выберите одну позицию, чтобы капнуть черную краску. Краска проникает сверху и течет вниз, увеличивая темноту всех ячеек на своем пути на $$$1$$$. После того как вы капнули краску, вы разворачиваете ленту.

Пусть $$$f(b)$$$ будет минимальным количеством операций, необходимых для достижения желаемой конфигурации. Можно доказать, что цель всегда может быть достигнута за конечное число операций.

Вам дан массив $$$a$$$ длины $$$n$$$. Найдите

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

по модулю $$$998\,244\,353$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — искомую сумму по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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(\mathtt{0})=0$$$
  • $$$f(a_1a_2)=f(\mathtt{01})=1$$$
  • $$$f(a_1a_2a_3)=f(\mathtt{010})=1$$$
  • $$$f(a_2)=f(\mathtt{1})=1$$$
  • $$$f(a_2a_3)=f(\mathtt{10})=1$$$
  • $$$f(a_3)=f(\mathtt{0})=0$$$

Это в сумме дает $$$0+1+1+1+1+0 = 4$$$

Во втором наборе входных данных, $$$f(a_1a_2a_3a_4a_5a_6) = 2$$$. Вот одна возможная последовательность операций.