미즈하시 파르시에게는 두 가지 취미가 있다. 하나는 제목과 무관한 디스크립션을 쓰는 것이고, 다른 하나는 복잡한 히스토그램 문제를 출제하는 것이다.

당신에게 $N$개의 기둥으로 이루어진 히스토그램이 주어진다. 해당 히스토그램의 각 기둥의 너비는 $1$이고, 왼쪽에서 $i$번째 기둥의 높이는 $H_i$이다.

세 양의 정수 $1\le L\le R\le N, 1\le K\le 10^9$에 대해서, $f(L,R,K)$를 다음 문제의 답으로 정의하자.

• 왼쪽에서 $L$번째와 $R$번째 사이의 히스토그램만을 고려할 때, 해당 히스토그램에 포함되는 높이 $K$인 직사각형의 최대 너비를 구하여라.

당신은 $\sum_{L=1}^N \sum_{R=L}^N \sum_{K=1}^{10^9} f(L,R,K) $를 $998,244,353$으로 나눈 나머지를 구해야 한다.

제약 조건

• $2 \le N \le 2^{17}$
• 모든 $1\le i\le N$에 대해서, $1\le H_i\le 10^9$

부분문제

1. (9점) $N\le 50, \max_{i=1}^N H_i\le 50$.

2. (8점) $N\le 2^7$.

3. (8점) $N\le 2^8$.

4. (9점) $N\le 2^9$.

5. (8점) $N\le 2^{10}$.

6. (8점) $N\le 2^{11}$.

7. (8점) $N\le 2^{12}$.

8. (9점) $N\le 2^{13}$.

9. (8점) $N\le 2^{14}$.

10. (8점) $N\le 2^{15}$.

11. (8점) $N\le 2^{16}$.

12. (9점) 추가 제약 조건 없음.

입력 형식

첫째 줄에 양의 정수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $H_1,H_2,\cdots,H_N$이 공백으로 구분되어 주어진다.

출력 형식

$\sum_{L=1}^N \sum_{R=L}^N \sum_{K=1}^{10^9} f(L,R,K) $를 $998,244,353$으로 나눈 나머지를 출력하라.

예제

예제 1

입력

10
6 4 10 8 5 8 6 1 7 2

출력

1148