#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,d;
cin >> n >> d;
assert(d==1);
int c[n];
for(int &i : c){
cin >> i;
}
const int lg = 20;
const int inf = 1e18;
int lef[n][lg];
int ans[n][lg];
map<int,int>mp;
mp[-1]=-1;
int pref[n];
ans[0][0]=0;
pref[0]=c[0];
lef[0][0]=-1;
mp[c[0]]=0;
for(int i = 1;i<n;i++){
auto it = mp.upper_bound(c[i]);
--it;
lef[i][0]=(*it).second;
pref[i]=c[i];
if(i){
pref[i]+=pref[i-1];
}
int sum=pref[i-1];
if(lef[i][0]>=0)
sum-=pref[lef[i][0]];
sum-=(i-lef[i][0]-1)*c[i];
ans[i][0]=sum;
mp[c[i]]=i;
}
for(int i = 0;i<n;i++){
fill(lef[i]+1,lef[i]+lg,-1);
fill(ans[i]+1,ans[i]+lg,inf);
for(int j = 1;j<lg;j++){
if(lef[i][j-1]<0)
break;
lef[i][j]=lef[lef[i][j-1]][j-1];
ans[i][j]=ans[i][j-1]+ans[lef[i][j-1]][j-1];
}
}
int q;
cin >> q;
while(q--){
int l,r;
cin >> l >> r;
l--;r--;
int curr = 0;
for(int i = lg-1;i>=0;i--){
if(lef[r][i]>=l){
curr+=ans[r][i];
r=lef[r][i];
}
}
assert(lef[r][0]<l);
curr+=pref[r];
if(l){
curr-=pref[l-1];
}
curr-=(r-l+1)*c[r];
cout << curr << "\n";
}
return 0;
}
