#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
const int maxn = 3e5+100;
const int LOGN = 20;
int arr[maxn];
int st[maxn][LOGN];
int lg[maxn];
int up[maxn][LOGN];
int ss[maxn][LOGN];
template<typename T>
void dbg(const T& t){
cout<<t<<endl;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
cout<<t<<" , ";
dbg(args...);
}
#define dbg(...) cout<<"( "<<#__VA_ARGS__<<" ) : ";dbg(__VA_ARGS__);
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
lg[1] = 0;
for(int i=2;i<maxn;i++) lg[i] = lg[i>>1]+1;
int n,d;
cin>>n>>d;
for(int i = 1;i<=n;i++){
cin>>arr[i];
st[i][0] = arr[i];
}
for(int j = 1;j<LOGN;j++){
for(int i = 1;i+(1LL<<j)<=n+1;i++){
st[i][j] = min(st[i][j-1],st[i+(1LL<<(j-1))][j-1]);
}
}
auto query = [&](int l,int r){
int k = r-l+1;
k = lg[k];
return min(st[l][k],st[r-(1LL<<k)+1][k]);
};
int pref[n+1];memset(pref,0,sizeof(pref));
for(int i = 1;i<=n;i++){
pref[i] = arr[i];
if(i) pref[i]+=pref[i-1];
}
auto sum = [&](int l,int r){
if(l>r) return 0LL;
if(l==0) return pref[r];
return pref[r]-pref[l-1];
};
int next[n+1];memset(next,0,sizeof(next));
next[1] = 0;
for(int i = 2;i<=n;i++){
next[i] = i-1;
while(next[i]!=0&&arr[i]<arr[next[i]]){
next[i] = next[next[i]];
}
}
for(int i=1;i<=n;i++){
int l = next[i],r = i;
int w = 0;
if(l==0){
w = 0;
}else{
int x = arr[next[i]];
w = -(r-l)*x;
}
// dbg(l,r,w)
up[i][0] = l;
ss[i][0] = w;
}
for(int j = 1;j<LOGN;j++){
for(int i=1;i<=n;i++){
up[i][j] = up[up[i][j-1]][j-1];
ss[i][j] = ss[i][j-1]+ss[up[i][j-1]][j-1];
}
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
int s = sum(l,r);
int node = r;
int k = 0;
for(int j = LOGN-1;j>=0;j--){
int x = up[node][j];
if(x<l){
continue;
}
k+=ss[node][j];
node = x;
}
k+=-(node-l) * arr[node];
// dbg(l,r,node,k)
k+=-arr[r];
cout<<s+k<<endl;
}
}
