Определим значение красоты последовательности \(b_1,b_2,\ldots,b_c\) как максимальное значение \(\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i\), где \(q\), \(s\), \(t\) являются целыми числами и \(s > q\) или \(t\leq q\). Обратите внимание, что \(b_i = 0\), когда \(i<1\) или \(i>c\), \(\sum\limits_{i=s}^{t}b_i = 0\), когда \(s>t\).
Например, если \(b = [-1,-2,-3]\), у нас может быть \(q = 0\), \(s = 3\), \(t = 2\), поэтому значение красоты равно \(0 + 0 = 0\). А если \(b = [-1,2,-3]\) и \(q = s = t = 2\), то значение красоты будет равно \(1 + 2 = 3\).
Вам дана последовательность \(a\) длины \(n\), определите сумму красоты всех непустых подотрезков \(a_l,a_{l+1},\ldots,a_r\) (\(1\leq l\leq r\leq n\)) последовательности \(a\).
Выведите ответ по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите строку, содержащую одно целое число — ответ по модулю \(998\,244\,353\).
Примечание
Во втором наборе входных данных для подпоследовательности \([-26,43,-41,34,13]\), когда \(q=5\), \(s=2\), \(t=5\), \(\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 23 + 49 = 72\).
В третьем наборе входных данных имеется только одна непустая последовательная подпоследовательность \([74]\). Когда \(q=1\), \(s=1\), \(t=1\), \(\sum\limits_{i=1}^{q}b_i + \sum\limits_{i=s}^{t}b_i = 148\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7
80 59 100 -52 -86 -62 75
8
-48 -14 -26 43 -41 34 13 55
1
74
20
56 -60 62 13 88 -48 64 36 -10 19 94 25 -69 88 87 79 -70 74 -26 59
|
5924
2548
148
98887
|