#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
const ll maxn = 300005;
ll tree[maxn*4];
ll lazy[maxn*4];
ll calc(ll k, ll x, ll y){
if (lazy[k] == -1) return tree[k];
else return lazy[k] * (y-x+1);
}
void push(ll k, ll x, ll y){
if (lazy[k] != -1){
lazy[k*2] = lazy[k];
lazy[k*2+1] = lazy[k];
tree[k] = lazy[k] * (y-x+1);
lazy[k] = -1;
}
}
void update(ll a, ll b, ll val, ll k=1, ll x=0, ll y = maxn-1){
if (a>y || b<x) return;
if (a<=x && y<=b){
lazy[k] = val;
return;
}
push(k,x,y);
ll mid = (x+y)/2;
update(a,b,val,k*2,x,mid);
update(a,b,val,k*2+1,mid+1,y);
tree[k] = calc(k*2,x,mid) + calc(k*2+1, mid+1, y);
}
ll query(ll a, ll b, ll k=1, ll x = 0, ll y = maxn-1){
if (a>y || b<x) return 0;
if (a<=x && y<=b){
return calc(k,x,y);
}
push(k,x,y);
ll mid = (x+y)/2;
return query(a,b,k*2,x,mid) + query(a,b,k*2+1,mid+1,y);
}
map<vector<ll>, ll> vals;
int main(){
FOR(i,0,maxn*4) tree[i] = 0, lazy[i] = -1;
ll n,d;
cin >> n >> d;
vector<ll> arr(n);
FOR(i,0,n) cin >> arr[i];
vector<ll> pref(n);
pref[0] = arr[0];
FOR(i,1,n) pref[i] = pref[i-1] + arr[i];
ll q;
cin >> q;
vector<vector<ll>> queries;
vector<vector<ll>> origqueries;
FOR(i,0,q){
ll temp1,temp2;
cin >> temp1 >> temp2;
temp1--;temp2--;
origqueries.push_back({temp1, temp2});
queries.push_back({temp2, temp1});
}
sort(queries.begin(), queries.end());
for (auto&i : queries) swap(i[0], i[1]);
ll cur = 0;
vector<ll> ans(q);
FOR(i,0,n){
update(i,i,arr[i]);
}
for (auto&i : queries){
while (cur <= i[1]){
ll lo = 0;
ll hi = cur;
while (lo < hi){
ll mid = (lo+hi)/2;
if (query(mid, mid) >= arr[cur]) hi = mid;
else lo = mid+1;
}
update(lo, cur, arr[cur]);
cur++;
}
vals[i] = (pref[i[1]]-pref[i[0]] + arr[i[0]]) - query(i[0], i[1]);
}
for (auto&i : origqueries) cout << vals[i] << "\n";
}
