#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
struct segtree{
ll n;
vector<ll>d;
segtree(ll n){
d.resize(4*n);
}
ll query(ll v,ll l,ll r,ll L,ll R){
if(R<L||r<L||R<l) return 0;
if(L<=l&&r<=R) return d[v];
ll mid=(l+r)>>1;
return query(v<<1,l,mid,L,R)+query(v<<1|1,mid+1,r,L,R);
}
void update(ll v,ll l,ll r,ll pos,ll val){
if(r<pos||pos<l) return;
if(l==r){
d[v]=val;
return;
}
ll mid=(l+r)>>1;
update(v<<1,l,mid,pos,val);
update(v<<1|1,mid+1,r,pos,val);
d[v]=d[v<<1]+d[v<<1|1];
}
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,d;
cin>>n>>d;
ll c[n+5],pre[n+5];
pre[0]=0;
for(ll i=1;i<=n;i++){
cin>>c[i];
pre[i]=pre[i-1]+c[i];
}
ll q;
cin>>q;
vector<array<ll,3>>que;
vector<ll>ans(q);
for(ll i=0;i<q;i++){
ll l,r;
cin>>l>>r;
que.pb({r,l,i});
}
segtree sg(n);
sort(all(que));
ll cur=0,sum=0;
vector<array<ll,3>>v;
for(ll R=1;R<=n;R++){
sum+=c[R];
ll cnt=1;
while(!v.empty()){
if(v.back()[2]>=c[R]){
cnt+=v.back()[1]-v.back()[0]+1;
v.pop_back();
}
else break;
}
v.pb({R-cnt+1,R,c[R]});
sg.update(1,0,n-1,v.size()-1,(pre[R]-pre[R-cnt])-cnt*c[R]);
while(cur<q&&que[cur][0]==R){
auto [r,l,j]=que[cur++];
array<ll,3>p;
p={l,n+5,0ll};
auto it=upper_bound(all(v),p)-v.begin();
ans[j]+=sg.query(1,0,n-1,it,v.size()-1);
ll L;
if(it==v.size()){
L=R+1;
}
else{
L=v[it][0];
}
it--;
ans[j]+=(pre[L-1]-pre[l-1])-(L-l)*v[it][2];
}
}
for(ll i=0;i<q;i++){
cout<<ans[i]<<"\n";
}
}
