Language: C++

///#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long
#define all(x) (x).begin(), (x).end()
#define finout(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
#define X first
#define Y second

using namespace std;
const int MOD = 1e9 + 7;

typedef pair <int, int> pii;
typedef vector <int> vi;
inline int ni() {int x; cin >> x; return x;}
template <class T>
inline T nt() {T x; cin >> x; return x;}
inline void print(){}
template<typename T, typename ...TAIL>
inline void print(const T &t, TAIL... tail) {cout << t; print(tail...);}
inline void input() {return;}
template<typename T, typename ...TAIL>
inline void input(T &t, TAIL&... tail) {cin >> t; input(tail...);}

const int N = 1001;
const int inf = 1e9 + 3;
const double PI = 3.14159265359;

signed main () {
///#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long
#define all(x) (x).begin(), (x).end()
#define finout(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
#define X first
#define Y second

using namespace std;
const int MOD = 1e9 + 7;

typedef pair <int, int> pii;
typedef vector <int> vi;
inline int ni() {int x; cin >> x; return x;}
template <class T>
inline T nt() {T x; cin >> x; return x;}
inline void print(){}
template<typename T, typename ...TAIL>
inline void print(const T &t, TAIL... tail) {cout << t; print(tail...);}
inline void input() {return;}
template<typename T, typename ...TAIL>
inline void input(T &t, TAIL&... tail) {cin >> t; input(tail...);}

const int N = 2 * 1005001;
const int inf = 1e9 + 7;
const double PI = 3.14159265359;

vector <pair <int, int> > q[N];

vi v;
int L;

int ans[N];

int pr[N];
int sfx[N];

int prAns[N];
int sfxAns[N];

void solve(int l, int r) {
  ///  cout << l << ' ' << r << '\n';
    if (l + 1 == r) {
        for (auto it : q[l]) {
            ans[it.second] = 1;
        }
        return;
    }
    for (int i = l; i < r; i++) {
        pr[i] = 0; sfx[i] = 0; prAns[i] = 0; sfxAns[i] = 0;
    }
    int m = (l + r) / 2;
    int last = m - 1;
    int curd = 0;
    int curAns = 1;
    int ssfx0 = 0, ppref0 = 0;
    for (int i = m - 1; i >= l; i--) {
        curd = abs(v[i] - v[last]);
        if (curd > L) {
            curd = 0;
            last = i + 1;
            curAns++;
        }
        if (curAns == 1) ssfx0 = curd;
        sfx[i] = curd;
        sfxAns[i] = curAns;
    }
    curd = 0;
    last = m;
    curAns = 1;
    for (int i = m; i < r; i++) {
        curd = abs(v[i] - v[last]);
        if (curd > L) {
            curd = 0;
            last = i - 1;
            curAns++;
        }
        if (curAns == 1) ppref0 = curd;
        pr[i] = curd;
        prAns[i] = curAns;
    }
    for (int i = m - 1; i >= l; i--) {
        while (!q[i].empty() && q[i].back().first >= m) {
            int l = i, r = q[i].back().first, ind = q[i].back().second;
            q[i].pop_back();
            int anss = prAns[r] + sfxAns[l];
            if ((prAns[r] > 1 ? ppref0 : pr[r]) + (sfxAns[l] > 1 ? ssfx0 : sfx[l]) + abs(v[m] - v[m - 1]) <= L) anss--;
            ans[ind] = anss;
        }

    }
    solve(l, m);
    solve(m, r);
}

signed main () {
    ios_base::sync_with_stdio(NULL);  cin.tie(0); cout.tie(0);
    int n = ni();
    for (int i = 0; i < n; i++) v.push_back(ni());
    L = ni();
    int Q = ni();
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        if (l > r) swap(l, r);
        q[l].push_back({r, i});
    }
    for (int i = 0; i < n; i++) {
        sort(all(q[i]));
    }
    solve(0, n);
    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }
}


















    return 0;
}

























Compiler output:
a.cc: In function 'int main()':
a.cc:42:14: warning: empty parentheses were disambiguated as a function declaration [-Wvexing-parse]
   42 | inline int ni() {int x; cin >> x; return x;}
      |              ^~
a.cc:42:14: note: remove parentheses to default-initialize a variable
   42 | inline int ni() {int x; cin >> x; return x;}
      |              ^~
      |              --
a.cc:42:14: note: or replace parentheses with braces to value-initialize a variable
a.cc:42:17: error: a function-definition is not allowed here before '{' token
   42 | inline int ni() {int x; cin >> x; return x;}
      |                 ^
a.cc:43:1: error: a template declaration cannot appear at block scope
   43 | template <class T>
      | ^~~~~~~~
a.cc:46:1: error: a template declaration cannot appear at block scope
   46 | template<typename T, typename ...TAIL>
      | ^~~~~~~~
a.cc:49:1: error: a template declaration cannot appear at block scope
   49 | template<typename T, typename ...TAIL>
      | ^~~~~~~~
a.cc:69:26: error: a function-definition is not allowed here before '{' token
   69 | void solve(int l, int r) {
      |                          ^
a.cc:124:13: warning: empty parentheses were disambiguated as a function declaration [-Wvexing-parse]
  124 | signed main () {
      |             ^~
a.cc:124:13: note: remove parentheses to default-initialize a variable
  124 | signed main () {
      |             ^~
      |             --
a.cc:124:13: note: or replace parentheses with braces to value-initialize a variable
a.cc:124:16: error: a function-definition is not allowed here before '{' token
  124 | signed main () {
      |                ^