#include <bits/stdc++.h>
using namespace std;

// ============================================================================
//  ROLLBACK DISJOINT SET UNION (DSU) WITH UNDO
// ============================================================================
// PURPOSE:
//   A DSU that supports rolling back the last union operations.
//   It does NOT use path compression (to allow rollback), only union by size,
//   so find() runs in O(log N).
//
// METHODS:
//   - RollbackDSU(int n)         : initialise n isolated elements (0..n-1)
//   - int find(int x)            : returns the root of x (no compression)
//   - bool unite(int a, int b)   : merges sets of a and b; returns true if merged
//   - int snapshot()             : returns a token (history size) for current state
//   - void rollback(int snap)    : restores DSU to the state at snap
//   - int sizeOfRoot(int x)      : returns size of the set containing x
//   - int getMaxSize()           : returns maximum component size over ALL elements
//
// TIME COMPLEXITY:
//   - find     : O(log N) (union by size)
//   - unite    : O(log N)
//   - rollback : O(number of undone operations * log N)
//
// NOTES:
//   - Elements are considered isolated even if not "active" in the current range.
//     Active status is managed outside (see MoRollbackSolver).
//   - The history stores enough information to restore maxSize correctly.
// ============================================================================
class RollbackDSU {
private:
    vector<int> parent, sz;
    struct Change {
        int child;      // root that became a child
        int parentRoot; // root that became the new parent
        int oldMax;     // value of maxSize before this union
    };
    vector<Change> history;
    int maxSize; // maximum component size among ALL elements (active + inactive)

public:
    RollbackDSU(int n) {
        parent.resize(n);
        sz.assign(n, 1);
        maxSize = (n > 0 ? 1 : 0);
        for (int i = 0; i < n; ++i) parent[i] = i;
        history.clear();
    }

    int find(int x) const {
        while (parent[x] != x) x = parent[x];
        return x;
    }

    // Returns true if a and b were in different sets (i.e., a union happened).
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b); // a becomes the new root
        // Save old state for rollback
        history.push_back({b, a, maxSize});
        parent[b] = a;
        sz[a] += sz[b];
        maxSize = max(maxSize, sz[a]);
        return true;
    }

    int snapshot() const {
        return (int)history.size();
    }

    void rollback(int snap) {
        while ((int)history.size() > snap) {
            Change ch = history.back();
            history.pop_back();
            parent[ch.child] = ch.child;
            sz[ch.parentRoot] -= sz[ch.child];
            maxSize = ch.oldMax;
        }
    }

    int sizeOfRoot(int x) const {
        return sz[find(x)];
    }

    int getMaxSize() const {
        return maxSize;
    }
};

// ============================================================================
//  QUERY STRUCTURE
// ============================================================================
struct Query {
    int l, r, idx; // inclusive range [l, r], original index
};

// ============================================================================
//  MO'S ALGORITHM WITH ROLLBACK DSU – SOLVER FOR RANGE CONNECTIVITY QUERIES
// ============================================================================
// PURPOSE:
//   Answers many queries on a static array. Each query asks for a property of
//   the graph formed by elements inside [l, r] with edges between adjacent
//   indices i and i+1 if they satisfy a condition (here: abs(a[i]-a[i+1]) <= K).
//
//   Two concrete queries are provided:
//     1) Maximum connected component size inside the range.
//     2) Number of connected components inside the range.
//
// HOW TO USE:
//   1) Build your array and a vector of Query {l, r, idx}.
//   2) Call maxComponentSizeInRange(arr, queries, K) or
//      countComponentsInRange(arr, queries, K).
//   3) The function returns a vector<int> where ans[idx] is the answer.
//
// TIME COMPLEXITY:
//   Let N = array size, Q = number of queries, B = block size (≈ N / sqrt(Q)).
//   For each block, the right pointer moves O(N), total O(N * (N/B)).
//   Left-pointer additions per query cost O(B), total O(Q * B).
//   With B ≈ N / sqrt(Q), total DSU operations: O((N+Q)*sqrt(N)*log N).
//
// CONSTRAINTS / ASSUMPTIONS:
//   - Array contains integers (int is fine; change to long long if needed).
//   - Queries are 0-indexed inclusive [l, r].
//   - K is an integer threshold (can be negative → no edges).
//   - If Q = 0, returns an empty vector.
//   - The connection condition is hard‑coded as a lambda – modify it to change the problem.
//
// NOTES:
//   - The DSU is reinitialised for each block of the MO order.
//   - Only active elements (inside the current range) are considered.
//   - Temporary left‑side additions are rolled back after each query.
// ============================================================================

// Helper: sort queries by block of l, then by r (ascending).
static vector<Query> buildBlockOrder(const vector<Query>& queries, int blockSize) {
    vector<Query> qs = queries;
    sort(qs.begin(), qs.end(), [&](const Query& a, const Query& b) {
        int blockA = a.l / blockSize;
        int blockB = b.l / blockSize;
        if (blockA != blockB) return blockA < blockB;
        return a.r < b.r;
    });
    return qs;
}

// ----------------------------------------------------------------------------
//  1) MAXIMUM CONNECTED COMPONENT SIZE INSIDE EACH RANGE
// ----------------------------------------------------------------------------
vector<int> maxComponentSizeInRange(const vector<int>& arr,
                                    const vector<Query>& queries,
                                    int K) {
    int n = (int)arr.size();
    int q = (int)queries.size();
    vector<int> ans(q, 0);
    if (q == 0) return ans;

    // Block size: a common choice is max(1, int(n / sqrt(q))).
    // You can adjust this for performance.
    int blockSize = max(1, (int)(n / max(1.0, sqrt((double)q))));

    vector<Query> ordered = buildBlockOrder(queries, blockSize);

    // active[i] == true if arr[i] is currently inside the "permanent" range
    vector<char> active(n, 0);

    // DSU with rollback; initially all isolated (but inactive).
    RollbackDSU dsu(n);

    // These track the state of ACTIVE components only.
    int activeComps = 0;
    int maxActiveSize = 0;

    // Core add operation: activate position p and connect it to active neighbours.
    // It updates activeComps and maxActiveSize.
    auto addCore = [&](int p) {
        if (active[p]) return; // should not happen, but safety
        active[p] = 1;
        activeComps++;
        maxActiveSize = max(maxActiveSize, 1);

        // Helper to connect p with q if q is active and the condition holds.
        auto tryConnect = [&](int q) {
            if (q < 0 || q >= n) return;
            if (!active[q]) return;
            // ---------- MODIFY THIS CONDITION FOR A DIFFERENT PROBLEM ----------
            bool condition = (abs(arr[p] - arr[q]) <= K);
            // -------------------------------------------------------------------
            if (!condition) return;
            if (dsu.find(p) == dsu.find(q)) return;
            // Save current sizes for updating maxActiveSize correctly.
            int szP = dsu.sizeOfRoot(p);
            int szQ = dsu.sizeOfRoot(q);
            if (dsu.unite(p, q)) {
                activeComps--;
                int newSize = szP + szQ;
                maxActiveSize = max(maxActiveSize, newSize);
            }
        };

        tryConnect(p - 1);
        tryConnect(p + 1);
    };

    // Snapshot of the state (history + active component stats)
    struct StateSnapshot {
        int histSize;
        int comps;
        int maxSize;
    };

    auto getStateSnapshot = [&]() -> StateSnapshot {
        return {dsu.snapshot(), activeComps, maxActiveSize};
    };

    auto restoreState = [&](const StateSnapshot& snap) {
        dsu.rollback(snap.histSize);
        activeComps = snap.comps;
        maxActiveSize = snap.maxSize;
    };

    // Process block by block
    int curBlock = -1;
    int curR = -1; // permanent right pointer
    int curL = -1; // permanent left pointer (used only internally)

    for (const Query& qry : ordered) {
        int block = qry.l / blockSize;
        if (block != curBlock) {
            // New block: reset everything
            curBlock = block;
            // Initialise empty permanent range: (blockEnd, blockEnd]
            int blockEnd = min(n - 1, (block + 1) * blockSize - 1);
            curR = blockEnd;
            curL = blockEnd + 1; // empty range

            // Reinitialise DSU and active array
            dsu = RollbackDSU(n);
            fill(active.begin(), active.end(), 0);
            activeComps = 0;
            maxActiveSize = 0;
        }

        // Expand right pointer permanently
        while (curR < qry.r) {
            ++curR;
            addCore(curR);
        }

        // Take a snapshot before adding temporary left elements
        StateSnapshot snap = getStateSnapshot();

        // Expand left pointer temporarily (we will rollback these additions)
        vector<int> tempAdded;
        while (curL > qry.l) {
            --curL;
            addCore(curL);
            tempAdded.push_back(curL);
        }

        // Answer the query using the current active components
        ans[qry.idx] = maxActiveSize;

        // Rollback temporary left additions
        restoreState(snap);
        for (int p : tempAdded) {
            active[p] = 0; // they are no longer in the range
        }
        // Reset curL to the right end of the block for the next query
        int blockEnd = min(n - 1, (block + 1) * blockSize - 1);
        curL = blockEnd + 1;
    }

    return ans;
}

// ----------------------------------------------------------------------------
//  2) NUMBER OF CONNECTED COMPONENTS INSIDE EACH RANGE
// ----------------------------------------------------------------------------
vector<int> countComponentsInRange(const vector<int>& arr,
                                   const vector<Query>& queries,
                                   int K) {
    int n = (int)arr.size();
    int q = (int)queries.size();
    vector<int> ans(q, 0);
    if (q == 0) return ans;

    int blockSize = max(1, (int)(n / max(1.0, sqrt((double)q))));
    vector<Query> ordered = buildBlockOrder(queries, blockSize);

    vector<char> active(n, 0);
    RollbackDSU dsu(n);
    int activeComps = 0;
    int maxActiveSize = 0; // not used here, but needed for snapshot struct

    auto addCore = [&](int p) {
        if (active[p]) return;
        active[p] = 1;
        activeComps++;
        maxActiveSize = max(maxActiveSize, 1);

        auto tryConnect = [&](int q) {
            if (q < 0 || q >= n) return;
            if (!active[q]) return;
            // ---------- MODIFY THIS CONDITION FOR A DIFFERENT PROBLEM ----------
            bool condition = (abs(arr[p] - arr[q]) <= K);
            // -------------------------------------------------------------------
            if (!condition) return;
            if (dsu.find(p) == dsu.find(q)) return;
            if (dsu.unite(p, q)) {
                activeComps--;
            }
        };

        tryConnect(p - 1);
        tryConnect(p + 1);
    };

    struct StateSnapshot {
        int histSize;
        int comps;
        int maxSize;
    };

    auto getStateSnapshot = [&]() -> StateSnapshot {
        return {dsu.snapshot(), activeComps, maxActiveSize};
    };

    auto restoreState = [&](const StateSnapshot& snap) {
        dsu.rollback(snap.histSize);
        activeComps = snap.comps;
        maxActiveSize = snap.maxSize;
    };

    int curBlock = -1;
    int curR = -1;
    int curL = -1;

    for (const Query& qry : ordered) {
        int block = qry.l / blockSize;
        if (block != curBlock) {
            curBlock = block;
            int blockEnd = min(n - 1, (block + 1) * blockSize - 1);
            curR = blockEnd;
            curL = blockEnd + 1;
            dsu = RollbackDSU(n);
            fill(active.begin(), active.end(), 0);
            activeComps = 0;
            maxActiveSize = 0;
        }

        while (curR < qry.r) {
            ++curR;
            addCore(curR);
        }

        StateSnapshot snap = getStateSnapshot();
        vector<int> tempAdded;
        while (curL > qry.l) {
            --curL;
            addCore(curL);
            tempAdded.push_back(curL);
        }

        ans[qry.idx] = activeComps;

        restoreState(snap);
        for (int p : tempAdded) {
            active[p] = 0;
        }
        int blockEnd = min(n - 1, (block + 1) * blockSize - 1);
        curL = blockEnd + 1;
    }

    return ans;
}

// ============================================================================
//  ADVANCED TRICKS & PATTERNS FOR MO + DSU
// ============================================================================
// 1) Custom connection condition:
//    Replace the line "bool condition = (abs(arr[p] - arr[q]) <= K);"
//    inside addCore with your own logic.
//
// 2) MO on trees:
//    Linearise the tree using Euler tour (tin/tout) and treat paths as ranges.
//
// 3) MO with updates (time dimension):
//    Extend MO with a time pointer and use the same rollback mechanism.
//
// 4) Block size:
//    A good starting point is max(1, int(n / sqrt(q))).
//    For n,q ≤ 1e5, blockSize ≈ 450 works well in practice.
// ============================================================================

// ============================================================================
//  EXAMPLE USAGE (main)
// ============================================================================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example array and queries
    vector<int> arr = {10, 20, 30, 25, 15, 5};
    int K = 10; // edge if |a[i] - a[i+1]| <= 10

    vector<Query> queries = {
        {0, 5, 0}, // whole array
        {1, 3, 1}, // [20, 30, 25]
        {2, 4, 2}  // [30, 25, 15]
    };

    // 1) Maximum component size
    vector<int> maxSizes = maxComponentSizeInRange(arr, queries, K);
    cout << "Max component sizes:\n";
    for (int i = 0; i < (int)queries.size(); ++i) {
        cout << "Query " << i << " [" << queries[i].l << ", " << queries[i].r
             << "] : " << maxSizes[i] << "\n";
    }

    // 2) Number of components
    vector<int> compCounts = countComponentsInRange(arr, queries, K);
    cout << "\nNumber of components:\n";
    for (int i = 0; i < (int)queries.size(); ++i) {
        cout << "Query " << i << " [" << queries[i].l << ", " << queries[i].r
             << "] : " << compCounts[i] << "\n";
    }

    return 0;
}