Rank Queries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)
#define ff     first
#define ss     second
#define pb     push_back
#define ppb    pop_back

template <typename T> using Ordered_Multiset_Tree =
        tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    _test
    {
        int n, q;
        cin>>n>>q;

        vector<int> a(n);
        for(auto &e: a)  cin>>e;

        vector<pair<int, int>> queries(q);
        for(auto &[e, f]: queries)  cin>>e>>f;

        vector<array<int, 3>> qer;
        for(int i=0; i<q; i++)
            qer.pb({queries[i].ff-1, queries[i].ss, i});

        sort(qer.begin(), qer.end());
        Ordered_Multiset_Tree<int> prv, nxt;
        vector<int> ans(q);

        for(auto e: a)      nxt.insert(e);

        int i = 0;
        int j = 0;

        for(auto [k, r, ind]: qer)
        {
            while(i < k)
                prv.insert(a[i++]);

            while(j <= k)
                nxt.erase(nxt.upper_bound(a[j++]));

            auto possible = [&](int rem)
            {
                int moreinPrv = prv.size() - prv.order_of_key(a[k]+1);
                int moreinNxt = nxt.size() - nxt.order_of_key(a[k]+1);

                moreinPrv = max(0, moreinPrv-rem);
                moreinNxt = max(0, moreinNxt-rem);

                return (moreinPrv + moreinNxt + 1 <= r);
            };

            int val = n-1;
            int low=0, high=n-1;

            while(low <= high)
            {
                int mid = (low + high)/2;

                if(possible(mid))
                    val=mid, high=mid-1;
                else
                    low=mid+1;
            }

            ans[ind] = val;
        }

        for(auto e: ans)
            cout<<e<<"\n";
    }
}