La función $f(a_1, a_2, \dots, a_n)$ representa la suma más grande de los elementos de un subsegmento no vacío en el arreglo $a_1, a_2, \dots, a_n$.

Se le da un arreglo $a_1, a_2, \dots, a_n$.

Puede gastar una moneda y disminuir cualquier elemento de $a$ en 1.

Otra función, $g(k)$, representa el valor más pequeño de $f(a_1, a_2, \dots, a_n)$ que puede lograr gastando como máximo $k$ monedas.

Encuentre $g(1) + g(2) + \dots + g(k)$. Como este valor puede ser muy grande, encuéntrelo módulo 998 244 353.

Entrada

La primera línea de la entrada contiene un entero, $n$ ($1 \le n \le 100\,000$): el número de elementos en $a$.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

La tercera línea contiene un entero $k$ ($1 \le k \le 10^{13}$).

Salida

Imprima $g(1) + g(2) + \dots + g(k)$, módulo 998 244 353.

Ejemplos

Entrada 1

5
1 -1 2 -2 3
3

Salida 1

5

Entrada 2

3
-3 -5 -35
1

Salida 2

998244349

Nota

En el primer ejemplo, $g(1) = 2, g(2) = 2, g(3) = 1$.

En el segundo ejemplo, $g(1) = -4$.