#160 모든연속부분수열의연속부분수열의합의최댓값의합

문제

길이 $N$ 의 정수 수열 $A_1,A_2,\cdots,A_N$ 이 주어진다.

연속 부분수열 $A_l,A_{l+1},\cdots,A_r$ 에 대해 을 다음과 같이 정의하자.

모든 $1 \le l \le r \le N$ 에 대한 $f(l,r)$ 의 합을 $998\,244\,353$ 으로 나눈 나머지를 출력하여라. 즉, 을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1$ $A_2$

문제의 답을 $998\,244\,353$ 으로 나눈 나머지를 출력한다. 출력할 때는 편의를 위해 답*2를 출력하라

#	Score	Constraints
1	7	$N \le 50$
2	13	$0 \le A_i \le 10^9$

Sample 1

Input

4
1 -2 3 -1

Output

17

출력할 때는 편의를 위해 답*2를 출력해야 하므로 $37$ 을 출력하면 된다.

Sample 2

Input

3
2 1 2

Output

16

출력할 때는 편의를 위해 답*2를 출력해야 하므로 $32$ 을 출력하면 된다.