#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
const int lim = 3e5 + 5;
const ll INF = 1e18;
int n, q;
ll d, c[lim];
namespace sub1{
void solve(){
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
ll mn = INF, ans = 0;
for(int i = r; i >= l; i--){
minimize(mn, c[i]);
if((c[i] - mn) % d != 0 && (mn -= d - (c[i] - mn) % d) < 0){
ans = -1;
break;
}
ans += (c[i] - mn) / d;
}
cout << ans << endl;
}
}
}
namespace sub2{
void solve(){
vector<int>left(n + 1), f(n + 1);
left[0] = f[0] = 0;
for(int i = 1; i <= n; i++){
left[i] = (c[i] == 0 ? i : left[i - 1]);
f[i] = f[i - 1] + c[i];
}
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
if(left[r] <= l){
cout << "0\n";
continue;
}
if(d == 1){
cout << f[left[r]] - f[l - 1] << "\n";
}
else{
cout << (f[left[r]] - f[l - 1] == 0 ? 0 : -1) << "\n";
}
}
}
}
namespace sub3{
void solve(){
vector<vector<pair<int, int>>>query(n + 1);
vector<ll>f(n + 1);
for(int i = f[0] = 0; i < q; i++){
int l, r;
cin >> l >> r;
query[r].emplace_back(l, i);
}
vector<ll>st(n << 2, 0), lazy(n << 2, -1);
auto push_down = [&] (int id, int l, int r, int m){
if(lazy[id] != -1){
st[id << 1] = (lazy[id << 1] = lazy[id << 1 | 1] = lazy[id]) * ll(m - l + 1);
st[id << 1 | 1] = lazy[id] * ll(r - m);
lazy[id] = -1;
}
};
function<void(int, int, int, int, int, ll)>update;
update = [&] (int id, int l, int r, int u, int v, ll x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
st[id] = (lazy[id] = x) * ll(r - l + 1);
return;
}
int m = (l + r) >> 1;
push_down(id, l, r, m);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = st[id << 1] + st[id << 1 | 1];
};
function<ll(int, int, int, int, int)>get;
get = [&] (int id, int l, int r, int u, int v){
if(l > v || r < u){
return 0LL;
}
if(u <= l && v >= r){
return st[id];
}
int m = (l + r) >> 1;
push_down(id, l, r, m);
return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
};
stack<int>stk;
vector<ll>ans(q);
for(int i = 1; i <= n; stk.push(i++)){
f[i] = f[i - 1] + c[i];
while(!stk.empty() && c[stk.top()] >= c[i]){
stk.pop();
}
update(1, 1, n, stk.empty() ? 1 : stk.top() + 1, i, c[i]);
for(auto& [l, I] : query[i]){
ans[I] = f[i] - f[l - 1] - get(1, 1, n, l, i);
}
}
for(ll& x : ans){
cout << x << "\n";
}
}
}
namespace sub4{
struct SegmentTree{
ll st[lim << 2], lazy[lim << 2];
bool apply;
SegmentTree(){}
SegmentTree(bool apply){
memset(lazy, (this->apply = apply) ? -1 : 0, sizeof(lazy));
memset(st, 0, sizeof(st));
}
void push_down(int id, int l, int r, int m){
if(apply && lazy[id] != -1){
st[id << 1] = (lazy[id << 1] = lazy[id << 1 | 1] = lazy[id]) * ll(m - l + 1);
st[id << 1 | 1] = lazy[id] * ll(r - m);
lazy[id] = -1;
}
else if(!apply && lazy[id] != 0){
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
st[id << 1] += lazy[id] * ll(m - l + 1);
st[id << 1 | 1] += lazy[id] * ll(r - m);
lazy[id] = 0;
}
}
void update(int id, int l, int r, int u, int v, ll x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
if(apply){
st[id] = (lazy[id] = x) * ll(r - l + 1);
}
else{
st[id] += x * ll(r - l + 1);
lazy[id] += x;
}
return;
}
int m = (l + r) >> 1;
push_down(id, l, r, m);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = st[id << 1] + st[id << 1 | 1];
}
ll get(int id, int l, int r, int u, int v){
if(l > v || r < u){
return 0;
}
if(u <= l && v >= r){
return st[id];
}
int m = (l + r) >> 1;
push_down(id, l, r, m);
return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
}
};
SegmentTree add(false), app(true);
vector<pair<int, int>>query[lim];
ll f[lim], ans[lim];
void solve(){
for(int i = f[0] = 0; i < q; i++){
int l, r;
cin >> l >> r;
query[r].emplace_back(l, i);
}
for(int i = 1; i <= n; i++){
int low = 1, high = i - 1, p = i;
ll a = c[i] / d, b = c[i] % d;
bool flag = (i > 1 && b < c[i - 1] % d);
while(low <= high){
int mid = (low + high) >> 1;
if(app.get(1, 1, n, mid, mid) >= a){
high = (p = mid) - 1;
}
else{
low = mid + 1;
}
}
app.update(1, 1, n, p, i, a);
if(flag){
add.update(1, 1, n, 1, i - 1, 1);
add.update(1, 1, n, 1, p - 1, -1);
}
f[i] = f[i - 1] + c[i] - b;
for(auto& [l, I] : query[i]){
ans[I] = (app.get(1, 1, n, l, l) - add.get(1, 1, n, l, l) < 0 ? -1 : (f[i] - f[l - 1] - (app.get(1, 1, n, l, i) - add.get(1, 1, n, l, i)) * d) / d);
}
}
for(int i = 0; i < q; i++){
cout << ans[i] << "\n";
}
}
}
namespace sub5{
pair<int, ll>up[lim][19];
ll b[lim], _c[lim], f[lim];
void solve(){
_c[0] = 0;
for(int i = 1; i <= n; i++){
b[i] = c[i] / d;
if((_c[i] = c[i] % d) < _c[i - 1]){
ll difference = (_c[i - 1] - _c[i] + d - 1) / d;
b[i] -= difference;
_c[i] += difference * d;
}
f[i] = f[i - 1] + b[i];
}
stack<int>st;
for(int i = 1; i <= n; st.push(i++)){
while(!st.empty() && b[st.top()] > b[i]){
st.pop();
}
if(!st.empty()){
int left = st.top();
up[i][0] = make_pair(left, f[i] - f[left] - b[i] * ll(i - left));
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j < 19; j++){
up[i][j] = make_pair(up[up[i][j - 1].first][j - 1].first, up[i][j - 1].second + up[up[i][j - 1].first][j - 1].second);
}
}
for(int _ = 0; _ < q; _++){
int l, r;
cin >> l >> r;
ll ans = 0;
for(int i = 18; i > -1; i--){
if(up[r][i].first >= l){
ans += up[r][i].second;
r = up[r][i].first;
}
}
cout << (c[l] < (b[l] - b[r]) * d ? -1 : ans + f[r] - f[l - 1] - b[r] * ll(r - l + 1)) << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> d;
for(int i = 1; i <= n; i++){
cin >> c[i];
}
cin >> q;
if(max(n, q) <= 3000){
sub1::solve();
}
else if(*max_element(c + 1, c + n + 1) <= 1){
sub2::solve();
}
else if(d == 1){
sub3::solve();
}
else{
bool is_sub4 = true;
for(int i = 1; i < n; i++){
if(c[i] < c[i + 1]){
is_sub4 = false;
break;
}
}
if(is_sub4){
sub4::solve();
}
else{
sub5::solve();
}
}
}
