Shared code

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int maxn = 200000 + 1;
LL bit[maxn];
void add(int x, LL v){
    for(; x < maxn; x += x & -x) bit[x] += v;
}
LL sum(int x){
    LL res = 0;
    for(; x; x -= x & -x) res += bit[x];
    return res;
}
int a[maxn], b[maxn], p[maxn];
LL x[maxn], v[maxn], ans[maxn];
vector<int> test[maxn];
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i += 1){
        cin >> x[i];
        p[i] = i;
    }
    for(int i = 1; i <= q; i += 1){
        cin >> a[i] >> b[i];
        test[0].push_back(i);
    }
    sort(p + 1, p + n + 1, [&](const int& i, const int& j){
        return x[i] < x[j];
    });
    for(int i = 1; i <= n; i += 1) v[i] = x[p[i]];
    for(int i = 0; i <= n; i += 1){
        if(i) add(p[i], v[i]);
        for(int j : test[i]){
            ans[j] = sum(b[j]) - sum(a[j] - 1) + 1;
            int p = upper_bound(v, v + n + 1, ans[j]) - v - 1;
            if(p > i) test[p].push_back(j);
        }
    }
    for(int i = 1; i <= q; i += 1) cout << ans[i] << '\n';
    return 0;
}