#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
void solve();
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
return 0;
}
int k;
int n, q;
vector<int> a;
void solve() {
cin >> n >> k;
a.resize(n); for (auto &u: a) cin >> u;
vector<int> pref=a; for (int i=1; i<n; i++) pref[i]+=pref[i-1];
cin >> q;
vector<vector<int>> queries;
vector<int> ans(q, -1);
for (int i=0; i<q; i++) {
int l, r; cin >> l >> r; l--, r--;
queries.pb({l, r, i});
ans[i]=pref[r]-(l?pref[l-1]:0);
}
int SQRT=sqrt(n);
sort(all(queries), [&](auto &x, auto &y){
if (x[0]/SQRT==y[0]/SQRT) return x[1]<y[1];
return x[0]/SQRT<y[0]/SQRT;
});
deque<int> dq;
int L=queries[0][0], R=queries[0][0]-1, val=0;
for (int i=0; i<q; i++) {
int l=queries[i][0], r=queries[i][1];
if (i && queries[i-1][0]/SQRT!=l/SQRT) {
dq.clear();
L=l, R=l-1, val=0;
}
while (R<r) {
R++;
while (!dq.empty() && a[dq.back()]>a[R]) {
int nb=dq.back();
dq.pop_back();
if (dq.empty()) val-=a[nb]*(nb-L+1);
else val-=a[nb]*(nb-dq.back());
}
if (dq.empty()) val+=(R-L+1)*a[R];
else val+=(R-dq.back())*a[R];
dq.push_back(R);
}
while (L>l) {
L--;
if (dq.empty() || a[L]<a[dq.front()]) dq.push_front(L), val+=a[L];
else val+=a[dq.front()];
}
while (L<l) {
val-=a[dq.front()];
if (dq.front()==L) dq.pop_front();
L++;
}
ans[queries[i][2]]-=val;
}
for (auto &u: ans) cout << u << endl;
}
