Easiest Sum

The function $f(a\_1, a\_2, \ldots, a\_n)$ represents the largest sum of elements on a non-empty subsegment in the array $a\_1, a\_2, \ldots, a\_n$.

You are given an array $a\_1, a\_2, \ldots, a\_n$. 

You can spend one coin and decrease any element of $a$ by $1$.

Another function, $g(k)$, represents the smallest value of $f(a\_1, a\_2, \ldots, a\_n)$ you can achieve by spending at most $k$ coins.

Find $g(1) + g(2) + \ldots + g(k)$. As this value may be very large, find it modulo $998\\,244\\,353$.

The first line of input contains one integer, $n$ ($1 \leq n \leq 100\\,000$): the number of elements in $a$.

The second line contains $n$ integers $a\_1, a\_2, \ldots, a\_n$ ($-10^8 \leq a\_i \leq 10^8$).

The third line contains one integer $k$ ($1 \leq k \leq 10^{13}$).

Print $g(1) + g(2) + \ldots + g(k)$, modulo $998\\,244\\,353$.

In the first example, $g(1)=2, g(2)=2,g(3)=1$.

In the second example, $g(1)=-4$.