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

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

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

• $f(l,r)$은 $l \le x \le y \le r$를 만족하는 두 정수 $x,y$에 대한 값 $A_x+A_{x+1}+\cdots+A_y$ 중 최댓값이다.

모든 $1 \le l \le r \le N$에 대한 $f(l,r)$의 합을 $998\,244\,353$으로 나눈 나머지를 출력하여라. 즉, $\sum\limits_{l=1}^N \sum\limits_{r=l}^N f(l,r) \pmod {998\ 244\ 353}$을 구하여라. 출력할 때는 편의를 위해 답*2를 출력하라

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

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

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

• $1 \le N \le 200\,000$
• $-10^9 \le A_i \le 10^9$
• 입력으로 주어지는 모든 수는 정수이다.