def solve(Q, Queries):
    MAX_VAL = 100000  
    steps = [0] * (MAX_VAL + 1)
    def compute_steps(x):
        steps_count = 0
        while x > 0:
            x //= 4
            steps_count += 1
        return steps_count
    for i in range(1, MAX_VAL + 1):
        steps[i] = compute_steps(i)
    prefix = [0] * (MAX_VAL + 1)
    for i in range(1, MAX_VAL + 1):
        prefix[i] = prefix[i-1]+steps[i]
    results = []
    for query in Queries:
        L, R = query
        if L > 1:
            results.append(prefix[R] - prefix[L - 1]+steps[L])
        else:
            results.append(prefix[R]+steps[L])
    return results

vector<int> getFinalLocations(vector<int> locations, vector<int> movedFrom, vector<int> movedTo) {

    multiset<int> dataLocations(locations.begin(), locations.end());
    for (int i = 0; i < movedFrom.size(); ++i) {
        auto it = dataLocations.find(movedFrom[i]);
        if (it != dataLocations.end()) {
            dataLocations.erase(it);
        }
        dataLocations.insert(movedTo[i]);
    }
    vector<int> finalLocations(dataLocations.begin(), dataLocations.end());
    return finalLocations;
}

#include <bits/stdc++.h>
using namespace std;
int count_inversions(const string &s) {
    int n = s.size(), inv = 0;
    vector<int> freq(26, 0);
    for (int i = n - 1; i >= 0; --i) {
        int c = s[i] - 'a';
        for (int j = 0; j < c; ++j) inv += freq[j];
        freq[c]++;
    }
    return inv;
}

int getMinInversion(string s, string t) {
    int n = s.size(), m = t.size();
    vector<vector<int>> cs(n + 1, vector<int>(26, 0)), ct(m + 1, vector<int>(26, 0));

    for (int i = 1; i <= n; ++i) {
        cs[i] = cs[i - 1];
        cs[i][s[i - 1] - 'a']++;
    }
    for (int j = 1; j <= m; ++j) {
        ct[j] = ct[j - 1];
        ct[j][t[j - 1] - 'a']++;
    }

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
    dp[0][0] = 0;

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (i < n) {
                int inv = 0;
                for (int c = s[i] - 'a' + 1; c < 26; ++c) inv += ct[j][c];
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + inv);
            }
            if (j < m) {
                int inv = 0;
                for (int c = t[j] - 'a' + 1; c < 26; ++c) inv += cs[i][c];
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + inv);
            }
        }
    }

    int inv_s = count_inversions(s), inv_t = count_inversions(t);
    return dp[n][m] + inv_s + inv_t;
}

int solution(int n,vector<int>nums){
  priority_queue<long long, vector<long long>, greater<long long> > pq;
  long long S = 0;
  
  for(int i = 1;i <= n;i++){
    int x=nums[i-1];
    S += x;
    pq.push(x);
    
    while(S < 0){
      S -= pq.top();
      pq.pop();
    }
  }
  
  return (int) pq.size();
    }

class Solution {
public:
    int helper(vector<int> &nums, int k){
        int frequency = 0, ans = 0; ; 
        map<int, int> mapping; 
        for(int i = 0; i < nums.size(); ++i){
            ans += nums[i]; 
            if(ans == k){
                frequency++; 
            }
            if(mapping.find(ans - k) != mapping.end()){ 
                frequency += mapping[ans - k];
            }
            mapping[ans]++; 
        }
        return frequency;
    }
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int count = 0;
        for(int i = 0; i < matrix.size(); ++i){
            vector<int> result(matrix[0].size(), 0);
            for(int j = i; j < matrix.size(); ++j){ 
                for(int k = 0; k < matrix[0].size(); ++k){ 
                    result[k] += matrix[j][k];
                }
                count += helper(result, target);
            }
        }
        return count;
    }
};