#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define int long long
#define fir first
#define sec second
#define pb push_back
const int maxn=3e5,inf=-1e18;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,d;
cin>>n>>d;
int c[n+1];
for(int q=1;q<=n;q++)cin>>c[q];
vector<ii>qu[n+1];
int que; cin>>que;
int ans[que+1];
for(int q=1;q<=que;q++){
int l,r; cin>>l>>r;
qu[r].pb({l,q});
}
int pref[n+1];
pref[0]=0;
for(int q=1;q<=n;q++)pref[q]=pref[q-1]+c[q];
vector<ii>st;
st.pb({0,0});
for(int q=1;q<=n;q++){
while(st.size()>1 && c[q]<=c[st.back().fir])st.pop_back();
ii apa=st.back();
st.pb({q,apa.second+(q-st.back().fir)*c[q]});
for(auto [idx,hah] : qu[q]){
int mana=lower_bound(st.begin(),st.end(),make_pair(idx,inf))-st.begin();
int tot=st.back().second-st[mana-1].second-(idx-st[mana-1].fir-1)*c[st[mana].fir];
ans[hah]=pref[q]-pref[idx-1]-tot;
}
}
for(int q=1;q<=que;q++){
cout<<ans[q]<<endl;
}
}
