시그마 시그마 시그마 시그마

면접 대비

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

요약

정수 N개가 주어졌을 때, 중첩된 시그마 구간에서 max(A_k, A_l)의 합을 998244353으로 나눈 나머지로 구합니다.

문제

에릭은 이제 막 시그마를 배워서 시그마를 여러 개 이어 붙이는 놀이에 빠졌다. 오늘은 2와 3이 소수라서 불편하다는 이유로 시그마를 4개 이어 붙였다.

$N$ 개의 정수 $A_1, A_2, \cdots, A_N$ 이 주어질 때, 다음 값을 구하는 프로그램을 작성하시오.

$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \sum_{k=i}^{j-1} \sum_{l=k+1}^{j} \max(A_k, A_l)$

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

두 번째 줄에 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$ 이 주어진다.

정답을 $998\,244\,353$ 으로 나눈 나머지를 출력한다.