회의

$N$개의 산이 수평으로 한 줄로 늘어서 있다. 왼쪽에서 오른쪽으로 0번부터 $N-1$번까지 번호가 붙어 있으며, $i$번 산의 높이는 $H_i$이다($0 \le i \le N-1$). 각 산의 꼭대기에는 사람이 한 명씩 살고 있다.

$Q$개의 회의를 연다. 회의에는 0번부터 $Q-1$번까지 번호가 붙어 있다. $j$번 회의($0 \le j \le Q-1$)에는 $L_j$번 산부터 $R_j$번 산까지(양 끝 포함) 그 사이 산에 사는 모든 사람이 참석한다($0 \le L_j \le R_j \le N-1$). 각 회의마다 장소로 산 $x$를 하나 골라야 한다($L_j \le x \le R_j$). 고른 $x$에 따라 회의 비용이 정해지며, 계산 방법은 다음과 같다.

• 산 $y$($L_j \le y \le R_j$)에서 오는 참석자의 비용은 $x$번 산부터 $y$번 산까지(양 끝 포함) 산들의 높이 중 최댓값이다. 특히 $x$번 산에서 오는 참석자의 비용은 $H_x$이다.
• 회의 비용은 모든 참석자 비용의 합이다.

각 회의에 대해 가능한 회의 비용의 최솟값을 구하라. 참석자들은 회의가 끝나면 각자 자기 산으로 돌아가므로, 이전 회의는 이후 회의의 비용에 영향을 주지 않는다.

• $1 \le N \le 750{,}000$
• $1 \le Q \le 750{,}000$
• $1 \le H_i \le 1{,}000{,}000{,}000$ ($0 \le i \le N-1$)
• $0 \le L_j \le R_j \le N-1$ ($0 \le j \le Q-1$)
• $(L_j, R_j) \ne (L_k, R_k)$ ($0 \le j < k \le Q-1$)