가장 쉬운 합

시간 제한1초메모리 제한512 MB

요약

배열의 원소를 1씩 줄이는 동전을 최대 k개 써서 얻을 수 있는 최대 부분합의 최솟값을 구하고, 예산 1부터 k까지의 값을 모두 더한 뒤 998244353으로 나눈 나머지를 구합니다.

난이도: 어려움10점 중 9점
유형: 누적 합, 이분 탐색, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

배열 $a_1, a_2, \ldots, a_n$ 의 비어 있지 않은 연속 부분 구간에 있는 원소의 합 중 가장 큰 값을 $f(a_1, a_2, \ldots, a_n)$ 이라고 하자.

배열 $a_1, a_2, \ldots, a_n$ 이 주어진다. 코인 한 개를 쓰면 임의의 원소 하나를 1만큼 감소시킬 수 있다.

$g(k)$ 는 코인을 최대 $k$ 개까지 써서 얻을 수 있는 $f(a_1, a_2, \ldots, a_n)$ 의 최솟값이다.

$g(1) + g(2) + \ldots + g(k)$ 를 구하라. 이 값이 매우 클 수 있으므로 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

입력

첫째 줄에 정수 $n$ ( $1 \leq n \leq 100\,000$ )이 주어진다. 둘째 줄에는 $n$ 개의 정수 $a_1, a_2, \ldots, a_n$ ( $-10^8 \leq a_i \leq 10^8$ )이 주어진다. 셋째 줄에는 정수 $k$ ( $1 \leq k \leq 10^{13}$ )이 주어진다.

출력

$g(1) + g(2) + \ldots + g(k)$ 를 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

힌트

첫 번째 예시에서 $g(1)=2$ , $g(2)=2$ , $g(3)=1$ 이다.

두 번째 예시에서 $g(1)=-4$ 이다.

예제2

예제 1
입력
```
5
1 -1 2 -2 3
3
```
예상 출력
```
5
```
예제 2
입력
```
3
-3 -5 -35
1
```
예상 출력
```
998244349
```