#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+50;
const int SQRT = 610;
const int MAXA = 50;
const int MOD = 998244353;
const int LOG = 21;
const int INF = 1e16+100;
const int INF2 = 1e18;
const ld EPS = 1e-12;
int n, d, c[MAXN], ans[MAXN],pr[MAXN];
vector <pii> que[MAXN];
struct seg {
int st[4*MAXN], laz[4*MAXN];
void bd(int id, int l, int r){
laz[id] = -1;
if(l==r) return;
bd(lf,l,md); bd(rg,md+1,r);
}
void bnc(int id, int l, int r){
if(laz[id]==-1) return;
laz[lf] = laz[id]; st[lf] = (md-l+1) * laz[id];
laz[rg] = laz[id]; st[rg] = (r-md) * laz[id];
laz[id] = -1;
}
int que(int id, int l, int r, int x, int y){
if(x<=l && r<=y) return st[id];
if(r<x || y<l) return 0;
bnc(id,l,r);
return que(lf,l,md,x,y) + que(rg,md+1,r,x,y);
}
int upd(int id, int l, int r, int x, int y, int p){
if(x<=l && r<=y){
laz[id] = p;
return st[id] = (r-l+1) * p;
}
if(r<x || y<l) return st[id];
bnc(id,l,r);
return st[id] = upd(lf,l,md,x,y,p) + upd(rg,md+1,r,x,y,p);
}
} A;
signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>d;
for(int i=1; i<=n; i++){
cin >> c[i]; pr[i] = pr[i-1]+c[i];
}
int q; cin>>q;
for(int i=1; i<=q; i++){
int l, r; cin>>l>>r; que[r].pb({l,i});
}
vector <pii> vec; vec.pb({0, -INF});
for(int i=1; i<=n; i++){
while(!vec.empty() && vec.back().fi > c[i])
vec.pop_back();
A.upd(1,1,n,vec.back().se+1,i, c[i]);
for(auto [l,id] : que[i]){
ans[id] = pr[i]-pr[l-1] - A.que(1,1,n,l,i);
}
vec.pb({c[i], i});
}
for(int i=1; i<=q;i++) cout << ans[i] << " \n";
}
