스케이트 연습과 쿼리

당신은 주어진 스케이트 코스에서 $Q$번의 스케이트 연습을 하려고 한다. 전체 코스는 총 $N+2$개의 지점으로 이루어져 있으며, 각 지점은 고유한 번호가 부여되어 있다. 지점의 번호는 $0$번부터 시작하여 $N+1$번까지, 즉 $0,1,2,\ldots,N,N+1$ 순서로 붙어 있다.

$i$번째 연습에서는 $(L_i-1)$번 지점에서 연습을 시작하여 $L_i$번 지점부터 $R_i$번 지점까지를 순서대로 거친 뒤, $(R_i+1)$번 지점에서 연습을 끝낸다. 따라서 $i$번째 연습 경로는 $[L_i-1,L_i,\ldots,R_i,R_i+1]$와 같다. 매 연습 경로는 다를 수 있다.

이 연습은 $(L_i-1)$번 지점에서 $0$의 속력으로 출발하여, $(R_i+1)$번 지점에 $0$의 속력으로 도착한다. $k$번 지점에는 속력 제한 $V_k$가 있어, 다음으로 방문할 지점의 속력 제한을 초과하지 않도록 이동하는 사이에 속력을 조절해야 한다. 속력을 높일 때는 원하는 만큼 높일 수 있지만, 속력을 낮추는 경우에는 마지막으로 방문했던 지점에서의 속력에서 $1$만큼만 낮출 수 있다.

단, 시작 지점 $(L_i-1)$번과 도착 지점 $(R_i+1)$번을 제외한 위치에서 속력은 $0$이 될 수 없다. 속력을 변경하지 않고 그대로 유지하는 것도 가능하다. 지점별 속도 제한 $V_k$는 모든 연습에서 동일하다.

연습의 성과는 각 지점에서의 속력의 합과 같다. 스케이트 코스의 속력 제한이 주어졌을 때, 각 연습마다 얻을 수 있는 최대 연습 성과를 구해보자. 단 성과가 너무 커질 수 있으므로, 최대 성과를 $998\,244\,353$으로 나눈 나머지를 출력하여라.

첫째 줄에 두 정수 $N,Q$가 공백으로 구분되어 주어진다.

둘째 줄에 $N$개의 정수 $V_1,V_2,\ldots,V_N$이 공백으로 구분되어 주어진다.

다음 $Q$개의 줄 중 $i$번째 줄에는 두 정수 $L_i,R_i$가 공백으로 구분되어 주어진다.

각 연습마다 한 줄에 하나씩, 해당 연습에서 얻을 수 있는 최대 연습 성과를 $998\,244\,353$으로 나눈 나머지를 출력한다.

• $1 \le N,Q \le 10\ 000\ 000$
• $1 \le V_i \le 10^9$ $(1 \le i \le N)$
• $1 \le L_i \le R_i \le N$ $(1 \le i \le Q)$