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

using ll = long long;

// ===================================================================
// 1) Fenwick Tree (Binary Indexed Tree) – Basic Utility
//    Supports point updates and prefix sums.
//    Used in many offline algorithms.
// ===================================================================

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, int delta) {
        for (; idx <= n; idx += idx & -idx)
            bit[idx] += delta;
    }

    int sumPrefix(int idx) const {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx)
            res += bit[idx];
        return res;
    }

    int rangeSum(int l, int r) const {
        if (l > r) return 0;
        return sumPrefix(r) - sumPrefix(l - 1);
    }
};

// ===================================================================
// 2) Offline Range Sum Queries (no updates)
//    Given an array and many queries (L, R) – answer sum of a[L..R].
//    This is trivial with prefix sums, but we show the offline approach
//    using BIT as a pattern for more complex problems.
// ===================================================================

vector<ll> offlineRangeSum(const vector<ll>& arr,
                           const vector<pair<int,int>>& queries) {
    int n = arr.size();
    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + arr[i];
    vector<ll> ans(queries.size());
    for (size_t i = 0; i < queries.size(); ++i) {
        int l = queries[i].first, r = queries[i].second;
        ans[i] = pref[r + 1] - pref[l];
    }
    return ans;
}

// ===================================================================
// 3) Offline Counting of Distinct Elements in Range Queries
//    Problem: Given an array a[1..n] and Q queries (L, R),
//    count the number of distinct values in a[L..R].
//    Idea: Sort queries by R, maintain last occurrence of each value,
//    and use BIT to mark positions of last occurrences.
// ===================================================================

vector<int> countDistinctInRange(const vector<int>& a,
                                 const vector<pair<int,int>>& queries) {
    int n = a.size();
    int q = queries.size();
    vector<int> ans(q);
    vector<vector<pair<int,int>>> byRight(n + 1); // queries grouped by right endpoint
    for (int i = 0; i < q; ++i) {
        int l = queries[i].first, r = queries[i].second;
        byRight[r].push_back({l, i});
    }

    Fenwick bit(n);
    unordered_map<int, int> last; // value -> last position seen

    for (int r = 1; r <= n; ++r) {
        int val = a[r - 1];
        if (last.count(val)) {
            bit.add(last[val], -1);
        }
        last[val] = r;
        bit.add(r, 1);

        for (auto &p : byRight[r]) {
            int l = p.first, idx = p.second;
            ans[idx] = bit.rangeSum(l, r);
        }
    }
    return ans;
}

// ===================================================================
// 4) Count Subarrays with Sum in [L, R] (works for negative numbers)
//    Idea: prefix sums. For each prefix sum P[i], we need the number of
//    earlier prefix sums P[j] (j < i) with L <= P[i] - P[j] <= R.
//    Rearrange: P[i] - R <= P[j] <= P[i] - L.
//    Process i from 1..n, coordinate compress all prefix sums,
//    use BIT to count how many previous prefixes fall in that range.
// ===================================================================

ll countSubarraysSumInRange(const vector<int>& nums, ll L, ll R) {
    int n = nums.size();
    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + nums[i];

    // coordinate compression of all prefix sums
    vector<ll> comp = pref;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());

    auto getIdx = [&](ll x) {
        return int(lower_bound(comp.begin(), comp.end(), x) - comp.begin()) + 1;
    };

    Fenwick bit(comp.size());
    ll ans = 0;
    bit.add(getIdx(pref[0]), 1); // prefix 0

    for (int i = 1; i <= n; ++i) {
        // need pref[j] in [pref[i]-R, pref[i]-L]
        ll lo = pref[i] - R;
        ll hi = pref[i] - L;
        int left = int(lower_bound(comp.begin(), comp.end(), lo) - comp.begin()) + 1;
        int right = int(upper_bound(comp.begin(), comp.end(), hi) - comp.begin()); // exclusive -> index (1‑based) of first > hi
        if (left <= right) {
            ans += bit.rangeSum(left, right);
        }
        bit.add(getIdx(pref[i]), 1);
    }
    return ans;
}

// ===================================================================
// 5) Mo's Algorithm – for Range Queries
//    Example: answer sum of distinct elements in range, or frequency
//    queries. This template shows a generic Mo framework.
//    Usage: define add() and remove() functions, and compute answer
//    when moving pointers.
//    Complexity: O((N + Q) * sqrt(N))
// ===================================================================

struct MoQuery {
    int l, r, idx, block;
};

// Example: count number of distinct elements in [l,r] using Mo
vector<int> moDistinct(const vector<int>& a, const vector<pair<int,int>>& queries) {
    int n = a.size();
    int q = queries.size();
    int blockSize = max(1, (int)sqrt(n));

    vector<MoQuery> qs(q);
    for (int i = 0; i < q; ++i) {
        qs[i].l = queries[i].first;
        qs[i].r = queries[i].second;
        qs[i].idx = i;
        qs[i].block = qs[i].l / blockSize;
    }

    sort(qs.begin(), qs.end(), [](const MoQuery& a, const MoQuery& b) {
        if (a.block != b.block) return a.block < b.block;
        if (a.block & 1) return a.r > b.r; // odd-even optimization
        return a.r < b.r;
    });

    vector<int> ans(q);
    vector<int> freq(*max_element(a.begin(), a.end()) + 1, 0);
    int curL = 1, curR = 0; // 1-indexed, inclusive
    int distinct = 0;

    auto add = [&](int pos) {
        int val = a[pos - 1];
        if (freq[val] == 0) distinct++;
        freq[val]++;
    };
    auto remove = [&](int pos) {
        int val = a[pos - 1];
        freq[val]--;
        if (freq[val] == 0) distinct--;
    };

    for (const auto& qu : qs) {
        int L = qu.l, R = qu.r;
        while (curL > L) add(--curL);
        while (curR < R) add(++curR);
        while (curL < L) remove(curL++);
        while (curR > R) remove(curR--);
        ans[qu.idx] = distinct;
    }
    return ans;
}

// ===================================================================
// 6) Mo's Algorithm with Updates (Mo with modifications)
//    Maintains a time dimension. Use for queries with point updates.
//    Complexity: O((N + Q)^(5/3)).
//    Note: queries and updates are known offline. Each query must have
//    a 't' field = number of updates that happened before it.
//    This version uses a block size of N^(2/3).
// ===================================================================

struct MoUpdateQuery {
    int l, r, t, idx;
};

struct MoUpdate {
    int pos, oldVal, newVal;
};

vector<int> moWithUpdates(vector<int> arr,
                          const vector<MoUpdate>& updates,
                          const vector<MoUpdateQuery>& queries) {
    int n = arr.size();
    int q = queries.size();
    int u = updates.size();

    // Optimal block size for Mo with updates: N^(2/3)
    int block = max(1, (int)pow(n, 2.0/3.0));

    vector<MoUpdateQuery> qs = queries; // copy to sort
    sort(qs.begin(), qs.end(), [&](const MoUpdateQuery& a, const MoUpdateQuery& b) {
        int blockA_l = a.l / block, blockB_l = b.l / block;
        if (blockA_l != blockB_l) return blockA_l < blockB_l;
        int blockA_r = a.r / block, blockB_r = b.r / block;
        if (blockA_r != blockB_r) return blockA_r < blockB_r;
        return a.t < b.t;
    });

    vector<int> ans(q);
    // Coordinate compress values or use a large frequency array.
    // Here we assume values are up to 1e6; you can replace with unordered_map.
    vector<int> freq(1000005, 0);
    int curL = 0, curR = -1, curT = 0; // 0-indexed inclusive range
    int distinct = 0;

    auto add = [&](int pos) {
        int val = arr[pos];
        if (freq[val] == 0) distinct++;
        freq[val]++;
    };
    auto remove = [&](int pos) {
        int val = arr[pos];
        freq[val]--;
        if (freq[val] == 0) distinct--;
    };
    auto applyUpdate = [&](int t, bool forward) {
        int pos = updates[t].pos;
        int oldVal = updates[t].oldVal;
        int newVal = updates[t].newVal;
        if (forward) {
            if (curL <= pos && pos <= curR) {
                remove(pos);
                arr[pos] = newVal;
                add(pos);
            } else {
                arr[pos] = newVal;
            }
        } else {
            if (curL <= pos && pos <= curR) {
                remove(pos);
                arr[pos] = oldVal;
                add(pos);
            } else {
                arr[pos] = oldVal;
            }
        }
    };

    for (const auto& qu : qs) {
        while (curT < qu.t) applyUpdate(curT++, true);
        while (curT > qu.t) applyUpdate(--curT, false);
        while (curL > qu.l) add(--curL);
        while (curR < qu.r) add(++curR);
        while (curL < qu.l) remove(curL++);
        while (curR > qu.r) remove(curR--);
        ans[qu.idx] = distinct;
    }
    return ans;
}

// ===================================================================
// 7) Sweep Line: Count Points in Rectangles
//    Given N points (x,y) and Q queries each asking number of points
//    with x in [x1,x2] and y in [y1,y2].
//    Use offline sweep by x-coordinate, BIT over y.
//    Complexity: O((N+Q) log N)
// ===================================================================

struct Point {
    int x, y;
};

struct RectQuery {
    int x1, y1, x2, y2, idx, sign; // sign for inclusion-exclusion
};

vector<int> countPointsInRectangles(const vector<Point>& pts,
                                    const vector<pair<pair<int,int>, pair<int,int>>>& rects) {
    int n = pts.size();
    int q = rects.size();

    // compress y coordinates
    vector<int> ys;
    for (auto& p : pts) ys.push_back(p.y);
    for (auto& r : rects) {
        ys.push_back(r.first.second);
        ys.push_back(r.second.second);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    auto getY = [&](int y) {
        return int(lower_bound(ys.begin(), ys.end(), y) - ys.begin()) + 1;
    };

    vector<RectQuery> events;
    for (int i = 0; i < q; ++i) {
        int x1 = rects[i].first.first, y1 = rects[i].first.second;
        int x2 = rects[i].second.first, y2 = rects[i].second.second;
        // add events: at x2 (inclusive) with +, at x1-1 with -
        events.push_back({x2, y1, y2, i, +1});
        if (x1 > 1) events.push_back({x1 - 1, y1, y2, i, -1});
    }

    sort(events.begin(), events.end(), [](const RectQuery& a, const RectQuery& b) {
        return a.x1 < b.x1; // sort by x-coordinate (first field)
    });

    vector<Point> sortedPts = pts;
    sort(sortedPts.begin(), sortedPts.end(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });

    Fenwick bit(ys.size());
    vector<int> ans(q, 0);
    int p = 0;
    for (auto& ev : events) {
        int limitX = ev.x1;
        while (p < n && sortedPts[p].x <= limitX) {
            bit.add(getY(sortedPts[p].y), 1);
            p++;
        }
        int yl = getY(ev.y1);
        int yr = getY(ev.y2);
        int cnt = bit.rangeSum(yl, yr);
        ans[ev.idx] += ev.sign * cnt;
    }
    return ans;
}

// ===================================================================
// 8) Offline Dynamic Connectivity (DSU with rollback + Segment Tree over time)
//    Process edges added over time, answer connectivity queries.
//    Use Divide and Conquer on time (segment tree over time) + DSU rollback.
//    Complexity: O((N + M) log Q * α(N))
// ===================================================================

struct DSU {
    vector<int> parent, sz;
    vector<pair<int,int>> history; // (child, parent_before_merge)
    int comps;

    DSU(int n) : parent(n+1), sz(n+1, 1), comps(n) {
        iota(parent.begin(), parent.end(), 0);
    }

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

    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);
        history.push_back({b, parent[b]});
        parent[b] = a;
        sz[a] += sz[b];
        comps--;
        return true;
    }

    void rollback(int snap) {
        while ((int)history.size() > snap) {
            auto [b, oldParent] = history.back();
            history.pop_back();
            int a = parent[b];
            sz[a] -= sz[b];
            parent[b] = oldParent;
            comps++;
        }
    }

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

struct TimeEdge {
    int u, v, l, r; // active in [l, r]
};

struct TimeQuery {
    int time, u, v; // query at time: are u and v connected?
};

class SegmentTreeOverTime {
    int n; // number of time steps
    vector<vector<pair<int,int>>> tree; // each node stores edges (u,v)

    void addEdge(int node, int l, int r, int ql, int qr, int u, int v) {
        if (ql <= l && r <= qr) {
            tree[node].push_back({u, v});
            return;
        }
        int mid = (l + r) / 2;
        if (ql <= mid) addEdge(node*2, l, mid, ql, qr, u, v);
        if (qr > mid) addEdge(node*2+1, mid+1, r, ql, qr, u, v);
    }

public:
    SegmentTreeOverTime(int n) : n(n), tree(4*n + 5) {}

    void addEdge(int l, int r, int u, int v) {
        if (l > r) return;
        addEdge(1, 1, n, l, r, u, v);
    }

    void dfs(int node, int l, int r, DSU& dsu, const vector<TimeQuery>& queries, vector<bool>& ans) {
        int snap = dsu.snapshot();
        for (auto &e : tree[node]) {
            dsu.unite(e.first, e.second);
        }
        if (l == r) {
            // answer queries at this time
            for (auto &q : queries) {
                if (q.time == l) {
                    ans[q.u] = (dsu.find(q.u) == dsu.find(q.v)); // assuming q.u stores index
                }
            }
        } else {
            int mid = (l + r) / 2;
            dfs(node*2, l, mid, dsu, queries, ans);
            dfs(node*2+1, mid+1, r, dsu, queries, ans);
        }
        dsu.rollback(snap);
    }
};

// ===================================================================
// 9) Parallel Binary Search
//    When we have many queries and each can be answered by binary search
//    on a monotonic predicate, we can process all queries simultaneously.
//    Example: find k‑th smallest in range, or find minimal x such that ...
//    This is a skeleton; you need to implement the check() function.
// ===================================================================

struct PBSQuery {
    int l, r, k, idx; // example: query about k-th smallest in range [l,r]
    int low, high;    // answer range
};

// Placeholder for the check function.
// It should return true if the answer for this query is <= mid.
bool check(int mid, const PBSQuery& q) {
    // This depends on the problem.
    // You can preprocess data as mid increases.
    return true;
}

vector<int> parallelBinarySearch(int n, const vector<PBSQuery>& queries) {
    int q = queries.size();
    vector<int> lo(q), hi(q), ans(q);
    for (int i = 0; i < q; ++i) {
        lo[i] = queries[i].low;
        hi[i] = queries[i].high;
    }
    bool changed = true;
    while (changed) {
        changed = false;
        vector<vector<int>> bucket(n + 2); // max answer range
        for (int i = 0; i < q; ++i) {
            if (lo[i] < hi[i]) {
                int mid = (lo[i] + hi[i]) / 2;
                bucket[mid].push_back(i);
                changed = true;
            }
        }
        if (!changed) break;

        // Sweep over mid and apply updates to a data structure.
        // For each mid, we have a list of query indices.
        // We need to evaluate check(mid, query) for each query.
        // For example, if we need to answer "how many elements <= mid in range",
        // we can maintain a Fenwick tree of positions as we increment mid.
        // Here we just call the check function (which you must implement).
        for (int mid = 0; mid <= n; ++mid) {
            // apply changes to reach value 'mid'
            // ...
            for (int idx : bucket[mid]) {
                if (check(mid, queries[idx])) {
                    hi[idx] = mid;
                } else {
                    lo[idx] = mid + 1;
                }
            }
        }
    }
    for (int i = 0; i < q; ++i) ans[i] = lo[i];
    return ans;
}

// ===================================================================
// 10) CDQ Divide and Conquer (Example: 2D Partial Order)
//     Solves problems where we need to count points (x, y) that satisfy
//     x <= q.x and y <= q.y. Complexity O(N log N) for 2D.
//     This is a skeleton; the merge logic depends on the specific problem.
// ===================================================================

struct CDQPoint {
    int x, y, type, idx; // type: 0 for point, 1 for query (with sign)
};

// The function cdq(items, l, r) will be implemented with merge logic.
// The merge part typically uses BIT to count points from the left half
// that satisfy conditions for queries in the right half.
void cdq(vector<CDQPoint>& items, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    cdq(items, l, mid);
    cdq(items, mid + 1, r);

    // Merge step: count contributions from left half (type 0) to right half (type 1)
    // using a Fenwick tree over y-coordinates.
    // ...
    // Then merge the two halves back sorted by x.
}

// ===================================================================
// 11) Euler Tour + Offline Subtree Sum Queries
//     Flattens a tree into an array using Euler Tour, then answers subtree
//     sum queries offline with prefix sums or BIT.
//     Complexity: O(N + Q) after DFS.
// ===================================================================

vector<int> adj[100005];
int timer = 0;
int tin[100005], tout[100005];
int flat[100005]; // array representation of the tree (holds node id or value)

void dfs(int node, int parent) {
    tin[node] = ++timer;
    flat[timer] = node; // or value[node]
    for (int child : adj[node]) {
        if (child != parent) dfs(child, node);
    }
    tout[node] = timer;
}

// After DFS, a subtree query for node u becomes a range sum query on [tin[u], tout[u]]
// in the array 'flat'. You can answer it with prefix sums or BIT.

// ===================================================================
// 12) Two Pointers: Count Pairs with Sum <= K
//     Given two arrays, count pairs (i,j) such that a[i] + b[j] <= K.
//     Complexity O(N log N + M log M).
// ===================================================================

ll countPairsSumLE(vector<int>& a, vector<int>& b, ll K) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    ll ans = 0;
    int j = (int)b.size() - 1;
    for (int i = 0; i < (int)a.size(); ++i) {
        while (j >= 0 && a[i] + b[j] > K) --j;
        if (j < 0) break;
        ans += (j + 1);
    }
    return ans;
}

// ===================================================================
// main() – example usage (you can extend or modify)
// ===================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example: distinct elements in range
    vector<int> arr = {1, 2, 1, 3, 2, 4};
    vector<pair<int,int>> queries = {{1,3}, {2,5}, {3,6}};
    auto res = countDistinctInRange(arr, queries);
    cout << "Distinct in ranges: ";
    for (int x : res) cout << x << " ";
    cout << "\n";

    // Example: count subarrays with sum in [L,R]
    vector<int> nums = {1, -2, 3, 4, -1, 2};
    ll L = 1, R = 5;
    cout << "Number of subarrays with sum in [1,5]: " << countSubarraysSumInRange(nums, L, R) << "\n";

    // Example: Mo's algorithm distinct
    auto moRes = moDistinct(arr, queries);
    cout << "Mo distinct: ";
    for (int x : moRes) cout << x << " ";
    cout << "\n";

    return 0;
}