#include<bits/stdc++.h>
using namespace std;
const long long inf=1000000000010;
const int MAXN=300009;
long long pref[MAXN],mas[MAXN];
struct Node
{
int l,r;
vector<long long> val;
vector<long long> pref;
};
Node tree[4*MAXN];
void build(int n,int l,int r)
{
tree[n].l=l;
tree[n].r=r;
if(l==r)
{
tree[n].val={mas[l]};
tree[n].pref={mas[l]};
return;
}
build(2*n,l,(l+r)/2);
build(2*n+1,(l+r)/2+1,r);
int pos=upper_bound(tree[2*n].val.begin(),tree[2*n].val.end(),tree[2*n+1].val[0])-tree[2*n].val.begin();
for(int i=0;i<pos;i++)tree[n].val.push_back(tree[2*n].val[i]);
for(int i=pos;i<tree[2*n].val.size();i++)tree[n].val.push_back(tree[2*n+1].val[0]);
for(int i=0;i<tree[2*n+1].val.size();i++)tree[n].val.push_back(tree[2*n+1].val[i]);
tree[n].pref.push_back(tree[n].val[0]);
for(int i=1;i<tree[n].val.size();i++)
{
tree[n].pref.push_back(tree[n].pref.back()+tree[n].val[i]);
}
}
pair<long long,long long> query(int n,long long minNum)
{
int pos=upper_bound(tree[n].val.begin(),tree[n].val.end(),minNum)-tree[n].val.begin();
if(pos==0)
{
return {tree[n].val.size()*minNum,minNum};
}
return {tree[n].pref[pos-1]+(tree[n].val.size()-pos)*minNum,tree[n].val[0]};
}
pair<long long,long long> getAns(int n,int l,int r,long long minNum)
{
if(tree[n].l==l&&tree[n].r==r)
{
return query(n,minNum);
}
if(tree[2*n].r<l)
{
return getAns(2*n+1,l,r,minNum);
}
if(tree[2*n+1].l>r)
{
return getAns(2*n,l,r,minNum);
}
auto a=getAns(2*n+1,tree[2*n+1].l,r,minNum);
auto b=getAns(2*n,l,tree[2*n].r,a.second);
return {a.first+b.first,b.second};
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long N,D,Q,l,r;
cin>>N>>D;
for(int i=1;i<=N;i++)
{
cin>>mas[i];
pref[i]=pref[i-1]+mas[i];
}
build(1,1,N);
cin>>Q;
while(Q--)
{
cin>>l>>r;
cout<<pref[r]-pref[l-1]-getAns(1,l,r,inf).first<<'\n';
}
return 0;
}
