#include <bits/stdc++.h>
using namespace std;
#define L(x) ((x) + (x))
#define R(x) (L(x) + 1)
#define int long long
struct SegTree {
struct Node {
int mn, mx, tag;
};
int N;
long long K;
vector<Node> SEG;
void push(int id) {
SEG[L(id)].mn += SEG[id].tag, SEG[L(id)].mx += SEG[id].tag, SEG[L(id)].tag += SEG[id].tag;
SEG[R(id)].mn += SEG[id].tag, SEG[R(id)].mx += SEG[id].tag, SEG[R(id)].tag += SEG[id].tag;
SEG[id].tag = 0;
}
void pull(int id) {
SEG[id].mn = min(SEG[L(id)].mn, SEG[R(id)].mn);
SEG[id].mx = max(SEG[L(id)].mx, SEG[R(id)].mx);
}
void build(int ll, int rr, int id, vector<int> &a) {
if (ll == rr) {
SEG[id].mn = SEG[id].mx = a[ll];
} else {
int mm = ll + (rr - ll) / 2;
build(ll, mm, L(id), a);
build(mm + 1, rr, R(id), a);
pull(id);
}
SEG[id].tag = 0;
}
void mod(int ml, int mr, int x, int ll, int rr, int id) {
if (ml <= ll && rr <= mr) {
SEG[id].mn += x, SEG[id].mx += x, SEG[id].tag += x;
} else {
push(id);
int mm = ll + (rr - ll) / 2;
if (ml <= mm) {
mod(ml, mr, x, ll, mm, L(id));
}
if (mr > mm) {
mod(ml, mr, x, mm + 1, rr, R(id));
}
pull(id);
}
}
int qry(int ll, int rr, int id) {
if (ll == rr) {
if (SEG[id].mn <= 0) {
return -ll;
} else {
return ll;
}
} else {
push(id);
int mm = ll + (rr - ll) / 2;
if (SEG[L(id)].mn <= 0 || SEG[L(id)].mx >= K) {
return qry(ll, mm, L(id));
} else if (SEG[R(id)].mn <= 0 || SEG[R(id)].mx >= K) {
return qry(mm + 1, rr, R(id));
} else {
return N + 1;
}
}
}
SegTree (int _N, int _K) : N(_N), K(_K), SEG(vector<Node>(N * 4)) {}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, Q;
long long K;
cin >> N >> Q >> K;
vector<int> A(N + 1);
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
vector<int> pos(N + 1);
for (int i = 1; i <= N; i++) {
pos[i] = pos[i - 1] + A[i];
}
vector<int> a = {0}, s = {0};
for (int i = 1; i <= N; i++) {
for (int j = 0; j < A[i]; j++) {
if (i & 1) {
a.push_back(1);
} else {
a.push_back(-1);
}
s.push_back(s.back() + a.back());
}
}
int S = s.size() - 1;
SegTree seg(S, K);
seg.build(1, S, 1, s);
vector<int> p(s.size());
for (int i = 1; i <= S; i++) {
p[i] = K == 1 ? a[i] * i : seg.qry(1, S, 1);
seg.mod(i + 1, S, -a[i], 1, S, 1);
seg.mod(i, i, 1 - a[i], 1, S, 1);
}
vector<vector<int>> dbl(S + 3, vector(19, S + 1));
for (int i = S; i >= 1; i--) {
if (p[i] < 0) {
dbl[i][0] = dbl[-p[i] + 1][0];
} else {
dbl[i][0] = p[i];
}
}
for (int j = 1; j <= 18; j++) {
for (int i = 1; i <= S; i++) {
dbl[i][j] = dbl[min(S + 1, dbl[i][j - 1] + 1)][j - 1];
}
}
while (Q--) {
int L, R;
cin >> L >> R;
int l = pos[L - 1] + 1, r = pos[R], ans = 0;
for (int i = 18; i >= 0; i--) {
if (dbl[l][i] <= r) {
ans += (1 << i);
l = dbl[l][i] + 1;
}
}
cout << ans << '\n';
}
}
