Функция $f(a_1, a_2, \dots, a_n)$ представляет собой наибольшую сумму элементов на непустом подотрезке массива $a_1, a_2, \dots, a_n$.

Дан массив $a_1, a_2, \dots, a_n$. Вы можете потратить одну монету, чтобы уменьшить любой элемент массива $a$ на 1. Другая функция, $g(k)$, представляет собой наименьшее значение $f(a_1, a_2, \dots, a_n)$, которого можно достичь, потратив не более $k$ монет.

Найдите $g(1) + g(2) + \dots + g(k)$. Так как это значение может быть очень большим, найдите его по модулю $998\,244\,353$.

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

Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 100\,000$): количество элементов в массиве $a$. Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$). Третья строка содержит одно целое число $k$ ($1 \le k \le 10^{13}$).

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

Выведите $g(1) + g(2) + \dots + g(k)$ по модулю $998\,244\,353$.

Примеры

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

5
1 -1 2 -2 3
3

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

5

Примечание

В первом примере $g(1) = 2, g(2) = 2, g(3) = 1$.

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

3
-3 -5 -35
1

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

998244349

Примечание

Во втором примере $g(1) = -4$.