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

// ===================================================================
// This file contains a collection of algorithms based on the
// "Hilbert Order" (a space-filling curve) and "Mo's Algorithm".
//
// Mo's Algorithm: An offline technique to answer many range queries
// (e.g., [L, R]) on a static array. "Offline" means we read ALL
// queries first, reorder them to minimize the movement of two pointers
// (left and right), and then answer them in that order.
//
// Hilbert Order: A fancy way to draw a continuous curve through all
// points in a 2D grid. By ordering our queries (L, R) along this curve,
// we ensure that queries that are close together (similar L and R)
// are processed together, which minimizes the total number of pointer
// moves. This makes Mo's Algorithm very fast in practice.
//
// Each function is ready to be used as a "black box".
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
// ===================================================================

// ===================================================================
// 1) CORE HILBERT ORDER FUNCTION
//    This function assigns a unique integer "order" to a point (x, y)
//    on a 2D grid. Points that are physically close to each other
//    will have close order values.
// ===================================================================

// 1.1) Calculate the Hilbert Order value for a point (x, y).
//      Parameters:
//        - x, y: the coordinates of the point (must be >= 0).
//        - pow: the grid size is 2^pow x 2^pow. So if pow = 20, max
//          coordinate is about 1,048,575.
//        - rot: rotation parameter, usually pass 0.
//      Returns:
//        - A long long integer representing the order on the Hilbert curve.
//      Time complexity: O(pow) which is effectively O(log N) since pow is small (~20).
//      Constraint: x and y must be < 2^pow.
//      Note: The lower the difference between two order values, the closer
//            the points are in the 2D grid.
long long hilbertOrder(int x, int y, int pow, int rot) {
    if (pow == 0) return 0;
    int hpow = 1 << (pow - 1);          // half of the current block size
    int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
    seg = (seg + rot) & 3;              // apply rotation
    static const int rotateDelta[4] = {3, 0, 0, 1};
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
    int nrot = (rot + rotateDelta[seg]) & 3;
    long long subSquareSize = 1LL << (2 * pow - 2); // size of the quadrant
    long long ans = seg * subSquareSize;
    long long add = hilbertOrder(nx, ny, pow - 1, nrot);
    ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
    return ans;
}

// ===================================================================
// 2) MO'S ALGORITHM FRAMEWORK
//    This section provides the structures and comparators needed to
//    sort queries for Mo's Algorithm.
// ===================================================================

// 2.1) A structure to represent a range query.
//      Parameters:
//        - l: left index of the range (0-based, inclusive).
//        - r: right index of the range (0-based, inclusive).
//        - idx: the original index of the query (to store answers).
//        - order: the Hilbert order value (filled automatically).
struct MoQuery {
    int l, r, idx;
    long long order;
};

// 2.2) Comparator to sort queries by their Hilbert order.
//      Parameters:
//        - a, b: two MoQuery objects.
//      Returns:
//        - true if a should come before b.
//      Time complexity: O(1).
//      Note: This is the main trick! Sorting by this order minimizes
//            the total movement of the L and R pointers.
bool cmpByHilbert(const MoQuery& a, const MoQuery& b) {
    return a.order < b.order;
}

// 2.3) Alternative comparator for Mo's Algorithm using block decomposition.
//      This is the classic way to sort queries (by block of L, then R).
//      Hilbert order is usually faster, but this is easier to understand.
//      Parameters:
//        - a, b: two MoQuery objects.
//        - blockSize: the size of the block (usually sqrt(N)).
//      Returns:
//        - true if a should come before b.
bool cmpByBlock(const MoQuery& a, const MoQuery& b, int blockSize) {
    int blockA = a.l / blockSize;
    int blockB = b.l / blockSize;
    if (blockA != blockB) return blockA < blockB;
    // To optimize for odd/even blocks (reduce pointer jumps), we
    // alternate the sorting order of R.
    if (blockA & 1) return a.r > b.r;
    return a.r < b.r;
}

// ===================================================================
// 3) EXAMPLE: COUNT DISTINCT ELEMENTS IN RANGE
//    This is the classic "Hello World" problem for Mo's Algorithm.
//    We maintain a frequency map `freq` for the current window [L, R].
//    When we move a pointer, we update the frequency and the answer.
// ===================================================================

// 3.1) Process queries to count distinct elements in each range.
//      This function demonstrates how to use the Hilbert order sorting
//      to answer a specific problem.
//      Parameters:
//        - arr: the original array of integers (size N).
//        - queries: a vector of MoQuery objects. Their 'l', 'r', and 'idx'
//          must be filled. The function will fill the 'order' field and sort them.
//      Returns:
//        - A vector of integers containing the answer for each query
//          (in the same order as the original queries).
//      Time complexity: O((N + Q) * sqrt(N)) roughly, but Hilbert
//        reduces the constant factor significantly.
//      Constraint: arr elements can be any int (we use unordered_map).
vector<int> moDistinctElements(const vector<int>& arr, vector<MoQuery>& queries) {
    int n = arr.size();
    int q = queries.size();
    
    // Calculate Hilbert order for each query.
    // pow = 20 is enough for N up to ~1e6.
    for (auto &qu : queries) {
        // We treat the point as (L, R) in 2D space.
        qu.order = hilbertOrder(qu.l, qu.r, 20, 0);
    }
    
    // Sort queries using the Hilbert comparator.
    sort(queries.begin(), queries.end(), cmpByHilbert);

    // Data structures for the current window.
    unordered_map<int, int> freq; // frequency of each value in the window.
    int curL = 0, curR = -1;      // current window boundaries (inclusive).
    int curAns = 0;               // number of distinct elements in current window.

    // Lambda (small function) to add an element at index 'idx' to the window.
    auto add = [&](int idx) {
        int val = arr[idx];
        freq[val]++;
        if (freq[val] == 1) curAns++;
    };

    // Lambda to remove an element at index 'idx' from the window.
    auto remove = [&](int idx) {
        int val = arr[idx];
        freq[val]--;
        if (freq[val] == 0) curAns--;
    };

    vector<int> answers(q);
    for (auto &qu : queries) {
        // Move the left and right pointers to match the current query [qu.l, qu.r].
        while (curL > qu.l) add(--curL);
        while (curR < qu.r) add(++curR);
        while (curL < qu.l) remove(curL++);
        while (curR > qu.r) remove(curR--);
        
        // The answer for this query is the number of distinct elements.
        answers[qu.idx] = curAns;
    }
    return answers;
}

// ===================================================================
// 4) ADVANCED: MO'S ALGORITHM WITH UPDATES (3D MO)
//    Solves problems where array elements can change between queries.
//    This adds a third dimension: "time" (the update index).
// ===================================================================

// 4.1) Structure for a 3D query (range [L, R] at time T).
//      Parameters:
//        - l, r: the range boundaries.
//        - t: the time (how many updates were applied before this query).
//        - idx: original index of the query.
struct MoQuery3D {
    int l, r, t, idx;
};

// 4.2) Structure for an update operation.
//      Parameters:
//        - pos: the index in the array to update.
//        - newVal: the value to set at `pos`.
//        - oldVal: the previous value at `pos` (needed to rollback).
struct Update {
    int pos, newVal, oldVal;
};

// 4.3) Comparator for 3D Mo's Algorithm.
//      Sorts by block of L, then block of R, then time.
//      Parameters:
//        - a, b: two MoQuery3D objects.
//        - blockSize: the size of the L block (usually N^(2/3)).
//      Returns:
//        - true if a should come before b.
bool cmpByBlock3D(const MoQuery3D& a, const MoQuery3D& b, int blockSize) {
    int blockA_L = a.l / blockSize;
    int blockB_L = b.l / blockSize;
    if (blockA_L != blockB_L) return blockA_L < blockB_L;
    int blockA_R = a.r / blockSize;
    int blockB_R = b.r / blockSize;
    if (blockA_R != blockB_R) return blockA_R < blockB_R;
    return a.t < b.t;
}

// 4.4) Process 3D queries.
//      Note: This function is a template. You must supply your own
//      `add`, `remove`, and `applyUpdate` logic depending on the problem.
//      Parameters:
//        - arr: the initial array (will be copied/modified internally).
//        - queries: vector of 3D queries.
//        - updates: vector of updates (chronological).
//      Returns:
//        - vector of answers in the original order.
//      Time complexity: O((N + Q) * N^(2/3)).
//      Block size: we use ceil(N^(2/3)) (approximately).
vector<int> moWithUpdates(vector<int> arr, vector<MoQuery3D>& queries, vector<Update>& updates) {
    int n = arr.size();
    int q = queries.size();
    int u = updates.size();
    
    // Determine optimal block size for 3D Mo.
    int blockSize = pow(n, 2.0/3.0) + 1;   // +1 to avoid precision issues
    sort(queries.begin(), queries.end(), [&](const MoQuery3D& a, const MoQuery3D& b) {
        return cmpByBlock3D(a, b, blockSize);
    });

    vector<int> answers(q);
    int curL = 0, curR = -1, curT = 0;
    int curAns = 0; // This depends on the problem.
    unordered_map<int, int> freq; // Frequency data structure.

    // --- LAMBDA FUNCTIONS (YOU MUST FILL THESE BASED ON YOUR PROBLEM) ---
    // Here is an example for counting distinct elements.
    auto add = [&](int idx) {
        int val = arr[idx];
        freq[val]++;
        if (freq[val] == 1) curAns++;
    };
    auto remove = [&](int idx) {
        int val = arr[idx];
        freq[val]--;
        if (freq[val] == 0) curAns--;
    };
    auto applyUpdate = [&](int idx, int newVal) {
        // Apply a point update to the array.
        // idx: index in the array. newVal: the value to change it to.
        int oldVal = arr[idx];
        // If the update position is inside the current window, we must
        // update our data structure first.
        if (curL <= idx && idx <= curR) {
            freq[oldVal]--;
            if (freq[oldVal] == 0) curAns--;
            freq[newVal]++;
            if (freq[newVal] == 1) curAns++;
        }
        arr[idx] = newVal;
    };
    // ------------------------------------------------

    for (auto &qu : queries) {
        // Move time pointer forward.
        while (curT < qu.t) {
            applyUpdate(updates[curT].pos, updates[curT].newVal);
            curT++;
        }
        // Move time pointer backward.
        while (curT > qu.t) {
            curT--;
            applyUpdate(updates[curT].pos, updates[curT].oldVal);
        }
        // Move L and R pointers (same as standard Mo).
        while (curL > qu.l) add(--curL);
        while (curR < qu.r) add(++curR);
        while (curL < qu.l) remove(curL++);
        while (curR > qu.r) remove(curR--);
        
        answers[qu.idx] = curAns;
    }
    return answers;
}

// ===================================================================
// 5) ADVANCED: MO'S ALGORITHM ON TREES
//    Solves path queries on a tree (e.g., distinct values on a path).
//    Uses Euler Tour to convert a tree path into a range query.
// ===================================================================

// 5.1) Flatten a tree using Euler Tour (2*N length).
//      Parameters:
//        - adj: adjacency list of the tree (0-based).
//        - root: the root node of the tree (usually 0).
//      Returns:
//        - euler: vector containing each node when entered and exited.
//        - first: first occurrence index of each node in euler.
//        - last: last occurrence index of each node in euler.
//      Time complexity: O(N).
//      Explanation:
//        - When we enter node u, we push u to euler.
//        - Then we traverse its children.
//        - When we exit node u, we push u to euler again.
//        - A path between u and v becomes a range query on this euler tour.
void flattenTree(const vector<vector<int>>& adj, int root,
                 vector<int>& euler, vector<int>& first, vector<int>& last) {
    int n = adj.size();
    first.assign(n, -1);
    last.assign(n, -1);
    euler.clear();
    euler.reserve(2 * n);
    
    function<void(int, int)> dfs = [&](int u, int p) {
        first[u] = euler.size();
        euler.push_back(u);
        for (int v : adj[u]) {
            if (v == p) continue;
            dfs(v, u);
        }
        last[u] = euler.size();
        euler.push_back(u);
    };
    dfs(root, -1);
}

// 5.2) Process path queries on a tree using Mo's Algorithm.
//      Example: Count distinct values on the path between u and v.
//      Parameters:
//        - values: value of each node.
//        - adj: adjacency list.
//        - queries: list of {u, v} pairs (0-based).
//      Returns:
//        - vector of answers.
//      Time complexity: O((N+Q) * sqrt(N)).
//      Constraint: Works for trees (no cycles). Values can be any int.
//      Trick:
//        - If first[u] > first[v], swap(u, v).
//        - Let LCA = lca(u, v).
//        - If LCA == u, the range is [first[u], first[v]].
//        - Else, the range is [last[u], first[v]] and we must add LCA separately.
vector<int> moOnTreeQueries(const vector<int>& values, const vector<vector<int>>& adj,
                            vector<pair<int, int>>& treeQueries) {
    int n = adj.size();
    int q = treeQueries.size();
    
    // 1. Flatten the tree.
    vector<int> euler, first, last;
    flattenTree(adj, 0, euler, first, last);
    
    // 2. Precompute LCA (using Binary Lifting).
    int LOG = 1;
    while ((1 << LOG) <= n) LOG++;
    vector<vector<int>> up(n, vector<int>(LOG));
    vector<int> depth(n, 0);
    function<void(int,int)> dfs_lca = [&](int u, int p) {
        up[u][0] = p;
        for (int j = 1; j < LOG; j++) {
            up[u][j] = up[ up[u][j-1] ][j-1];
        }
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs_lca(v, u);
        }
    };
    dfs_lca(0, 0);
    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int j = LOG-1; j >= 0; j--) {
            if (diff & (1 << j)) u = up[u][j];
        }
        if (u == v) return u;
        for (int j = LOG-1; j >= 0; j--) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
        return up[u][0];
    };

    // 3. Build Mo queries.
    vector<MoQuery> moQueries;
    moQueries.reserve(q);
    vector<int> lcaNode(q, -1);
    for (int i = 0; i < q; i++) {
        int u = treeQueries[i].first;
        int v = treeQueries[i].second;
        int w = lca(u, v);
        lcaNode[i] = w;
        
        if (first[u] > first[v]) swap(u, v);
        if (w == u) {
            moQueries.push_back({first[u], first[v], i, 0});
        } else {
            moQueries.push_back({last[u], first[v], i, 0});
        }
    }

    // 4. Process Mo queries (using Hilbert order).
    //    We use an unordered_map for frequencies (supports any integer values).
    unordered_map<int, int> freq;           // frequency of node values
    vector<bool> inWindow(n, false);        // whether a node's value is currently counted
    int curAns = 0;
    auto addNode = [&](int nodeIdx) {
        int node = euler[nodeIdx];
        int val = values[node];
        if (inWindow[node]) {
            freq[val]--;
            if (freq[val] == 0) curAns--;
        } else {
            freq[val]++;
            if (freq[val] == 1) curAns++;
        }
        inWindow[node] = !inWindow[node];
    };

    // Sort queries by Hilbert order.
    for (auto &qu : moQueries) {
        qu.order = hilbertOrder(qu.l, qu.r, 20, 0);
    }
    sort(moQueries.begin(), moQueries.end(), cmpByHilbert);

    vector<int> ans(q);
    int curL = 0, curR = -1;
    for (auto &qu : moQueries) {
        while (curL > qu.l) addNode(--curL);
        while (curR < qu.r) addNode(++curR);
        while (curL < qu.l) addNode(curL++);
        while (curR > qu.r) addNode(curR--);
        
        // If the LCA is not part of the range, we need to add it manually.
        int l = lcaNode[qu.idx];
        if (inWindow[l]) {
            ans[qu.idx] = curAns;
        } else {
            // Add LCA temporarily, compute answer, then remove it.
            int val = values[l];
            freq[val]++;
            if (freq[val] == 1) curAns++;
            ans[qu.idx] = curAns;
            freq[val]--;
            if (freq[val] == 0) curAns--;
        }
    }
    return ans;
}

// ===================================================================
// 6) TRICKS & PATTERNS FOR COMPETITIONS
//    Additional useful utilities that rely on the Hilbert ordering
//    or general two-pointer advancements.
// ===================================================================

// 6.1) Count subarrays with sum in range [L, R] supporting NEGATIVE numbers.
//      Parameters:
//        - nums: vector of integers (can be negative!).
//        - L, R: the lower and upper bounds for the sum.
//      Returns:
//        - The number of subarrays with sum in [L, R].
//      Time complexity: O(N log N).
//      How it works:
//        1. Compute prefix sums P[0..N].
//        2. We need to count pairs (i < j) such that L <= P[j] - P[i] <= R.
//        3. As we iterate j from 0 to N, we count how many previous P[i]
//           are in the range [P[j] - R, P[j] - L] using a Fenwick tree.
//      Constraints: Works for all integers (positive, negative, zero).
long long countSubarraysInRangeWithNegatives(const vector<int>& nums, long long L, long long R) {
    int n = nums.size();
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
    
    // Coordinate compression for all values we will query or update.
    vector<long long> coords;
    coords.reserve(3 * (n + 1));
    for (long long x : pref) {
        coords.push_back(x);
        coords.push_back(x - L);
        coords.push_back(x - R);
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    
    auto getIdx = [&](long long x) {
        return int(lower_bound(coords.begin(), coords.end(), x) - coords.begin()) + 1;
    };
    
    // Fenwick Tree (Binary Indexed Tree) for prefix sums.
    struct Fenwick {
        int size;
        vector<int> bit;
        Fenwick(int s) : size(s), bit(s + 2, 0) {}
        void update(int idx, int delta) {
            while (idx <= size) {
                bit[idx] += delta;
                idx += idx & -idx;
            }
        }
        int query(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += bit[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
        int rangeQuery(int l, int r) {
            if (l > r) return 0;
            return query(r) - query(l - 1);
        }
    };
    
    Fenwick ft(coords.size());
    long long ans = 0;
    for (long long x : pref) {
        // We need previous P[i] >= x - R and <= x - L.
        int left = getIdx(x - R);
        int right = getIdx(x - L);
        ans += ft.rangeQuery(left, right);
        ft.update(getIdx(x), 1);
    }
    return ans;
}

// 6.2) Find the maximum sum of a subarray with length at least K.
//      Uses a prefix sum and a sliding window minimum (two-pointer/monotonic).
//      Parameters:
//        - nums: vector of integers (can be negative).
//        - k: minimum length of the subarray.
//      Returns:
//        - The maximum subarray sum with length >= k.
//      Time complexity: O(N).
//      Trick: Maintain the minimum prefix sum seen so far that is at least
//             k steps behind the current position.
long long maxSubarraySumAtLeastK(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
    
    long long ans = LLONG_MIN;
    deque<int> dq; // stores indices of prefix sums in increasing order of value.
    for (int i = 0; i <= n; i++) {
        // Remove indices that are too far away (i - idx < k -> idx <= i - k).
        while (!dq.empty() && dq.front() < i - k) dq.pop_front();
        // If we have a valid previous prefix, check the sum.
        if (!dq.empty()) {
            ans = max(ans, pref[i] - pref[dq.front()]);
        }
        // Maintain monotonicity (increasing values).
        while (!dq.empty() && pref[dq.back()] >= pref[i]) dq.pop_back();
        dq.push_back(i);
    }
    return ans;
}

// 6.3) Minimum operations to make all elements equal (using median).
//      This is a classic problem: each operation changes an element by +1/-1.
//      The optimal target is the median.
long long minOperationsToMakeEqual(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    sort(nums.begin(), nums.end());
    int median = nums[n / 2];
    long long totalCost = 0;
    for (int x : nums) {
        totalCost += std::abs((long long)x - (long long)median);
    }
    return totalCost;
}

// 6.4) Maximum number of pairs (one from A, one from B) with sum <= K.
//      Greedy algorithm using two pointers on sorted arrays.
//      Parameters:
//        - a, b: vectors of integers.
//        - K: upper bound for the sum.
//      Returns:
//        - Maximum number of disjoint pairs.
//      Time complexity: O(N log N + M log M).
int maxPairsWithSumAtMostK(vector<int>& a, vector<int>& b, int K) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int i = 0, j = b.size() - 1;
    int ans = 0;
    while (i < a.size() && j >= 0) {
        if (a[i] + b[j] <= K) {
            ans++;
            i++;
            j--;
        } else {
            j--;
        }
    }
    return ans;
}

// ===================================================================
// 7) GENERIC TWO-POINTER PATTERN (Placeholder reminder)
// ===================================================================
template<typename T>
int twoPointerPlaceholder(const vector<T>& arr) {
    int l = 0, r = arr.size() - 1;
    int ans = 0;
    while (l < r) {
        // Update ans based on arr[l], arr[r].
        // Move l++ or r-- based on a condition.
        if (arr[l] + arr[r] < 0) l++;
        else r--;
    }
    return ans;
}

// ===================================================================
// main() - Demonstration of how to use these black boxes.
// ===================================================================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example 1: Distinct elements in range queries.
    vector<int> arr = {1, 2, 1, 3, 4, 2, 1};
    vector<MoQuery> queries = {
        {1, 4, 0, 0}, // query 0: range [1, 4] -> 2,1,3,4 -> distinct = 4
        {0, 2, 1, 0}, // query 1: range [0, 2] -> 1,2,1 -> distinct = 2
        {2, 5, 2, 0}  // query 2: range [2, 5] -> 1,3,4,2 -> distinct = 4
    };
    vector<int> distinctAnswers = moDistinctElements(arr, queries);
    for (int i = 0; i < distinctAnswers.size(); i++) {
        cout << "Distinct in query " << i << ": " << distinctAnswers[i] << "\n";
    }

    // Example 2: Count subarrays with sum in [L, R] supporting negative numbers.
    vector<int> nums = {1, -2, 3, -4, 5};
    long long L = 1, R = 3;
    long long cnt = countSubarraysInRangeWithNegatives(nums, L, R);
    cout << "Number of subarrays with sum in [1, 3]: " << cnt << "\n";

    // Example 3: Maximum subarray sum with length at least 2.
    vector<int> nums2 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Max subarray sum with length >= 2: " << maxSubarraySumAtLeastK(nums2, 2) << "\n";

    return 0;
}