Meetings timer 6초 memory 768MB

N개의 산들이 존재하고 산들의 바닥은 수평선 위에 놓여있다.

산들에는 왼쪽에서 오른쪽으로 0부터 N-1의 번호가 붙어있다.

산 i의 높이는 H_i이다 (0 ≤ i ≤ N - 1).

각 산의 꼭대기에 정확히 한 사람이 산다.

당신은 Q개의 모임들을 개최할 것이다.

여기서 모임들은 0부터 Q-1로 나타낸다.

모임 j (0 ≤ j ≤ Q-1)에는 산 번호 L_j 이상 R_j 이하의 산들에 살고 있는 모든 사람들이 참석해야 한다 (0 ≤ L_j ≤ R_j ≤ N-1).

모임 j에 대해서, 당신은 모임 장소로 산 x를 선택해야 한다 (L_j ≤ x ≤ R_j).

이 선택에 따라 모임 의 비용이 다음과 같이 계산된다:

- 산 y (L_j ≤ y ≤ R_j)에 사는 참석자의 비용은 x와 y를 포함해서 x와 y사이 산들의 최대 높이다.

- 특별히 산 x에 사는 참석자의 비용은 산 x의 높이인 H_x이다.

- 모임의 비용은 모든 참석자들의 비용의 합이다.

각 모임에 대해서, 당신은 그 모임을 개최하는 최소 비용을 찾고 싶다.

각 모임 후에 모든 참석자들은 그들이 사는 산으로 돌아가므로 모임의 비용은 이전 모임들에 영향받지 않음에 주목하자.