외계 선인장

어떤 외계 행성의 지표면은 사막이 대부분이라 비가 별로 오지 않는다. 이 행성에 사는 식물은 모두 선인장이다. 비가 워낙 오지 않기 때문에, 선인장들은 서로 협력해서 물을 저장하는 방법을 가지도록 진화했다.

행성의 한 지역은 상하 방향과 좌우 방향만 존재하는 $2$차원 평면이다. 그 지역에 $N$개의 선인장이 일렬로 붙어 서 있다. 선인장의 폭은 모두 $1$미터이다. 선인장들의 높이는 서로 다를 수 있다. 환경미화를 위해서 $S$번째 선인장에서 $E$번째 선인장까지만 남긴 상태에서 비가 충분히 많이 내렸다. 그래서 선인장 위쪽에 물을 담을 수 있는 면적에 모두 물이 고였다고 한다. 즉, 아래 그림처럼 물이 고인다. 아래 그림에서 화살표로 표시된 범위 밖의 선인장은 없어진 것으로 생각해야 한다.

선인장들의 높이와 남아 있는 선인장들의 범위를 입력으로 받아 고인 물의 양을 면적으로 계산하는 프로그램을 작성하라. 남아 있는 선인장들의 범위는 최대 $Q$번 주어진다. 주어지는 범위는 항상 모든 선인장이 존재하는 초기 상태에 적용한다.

여러분은 다음 함수를 작성하여야 한다.

• void init( int H[] ) : 최초에 한번만 호출되는 함수이다. $H$는 제일 왼쪽 선인장부터 순서대로 선인장의 높이를 저장한 크기 $N$인 배열(vector)이다. $N$은 선인장의 개수이다.
• long long query( int S, int E ) : $S$번째 선인장부터 $E$번째 선인장까지 남긴 상태에서 충분히 많은 비가 내렸을 때 고인 물의 양을 면적으로 리턴해야 한다. ($1≤S≤E≤N$) 이 함수는 최대 $Q$번 호출된다. 모든 호출은 독립적이다. 즉, 한 호출에서 선인장이 없어진 것은 다른 호출과 무관하다.

• $1 \le N \le 500\\,000$
• $1 \le Q \le 500\\,000$
• 선인장의 높이는 $1$이상 $10^9$이하