수열과 쿼리 1

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

당신은 $Q$개의 쿼리를 처리해야 한다. 각 쿼리는 두 정수 $l, r$로 주어진다.

쿼리마다 정수 $k$를 $l \le k\le r$가 되도록 하나 고른다. 그 후 길이 $k-l+1$의 정수 수열 $B_l, B_{l+1}, \cdots, B_k$를 고른다. $B$는 다음 조건을 만족해야 한다.

• $B_l \le B_{l+1} \le \cdots \le B_k$
• 모든 $l\le i\le k$에 대해 $B_i\le A_i$이다.

이때 $B_l + B_{l+1} + \cdots + B_k$의 최댓값을 출력하여라.

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

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

다음 $Q$개의 줄에는 쿼리를 나타내는 두 정수 $l, r$가 공백으로 구분되어 주어진다.

각 쿼리마다 정답을 한 줄에 하나씩 출력한다.

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