Tracking Segments(二分,区间前缀)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,t,a[N],f[N],res,num,ans,m,ll[N],rr[N],q,s[N];
bool vis[N];
bool check(int u)
{
    for(int i=1;i<=n;i++) s[i]=0,f[i]=0;
    for(int i=1;i<=u;i++) f[a[i]]=1;
    for(int i=1;i<=n;i++) s[i]=s[i-1]+f[i];
    for(int i=1;i<=m;i++){
        if((s[rr[i]]-s[ll[i]-1])*2>(rr[i]-ll[i])+1) return true;
    }
    return false;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=m;i++) cin>>ll[i]>>rr[i];
        cin>>q;
        for(int i=1;i<=q;i++) cin>>a[i];
        int l=1,r=q+1,flag=0;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid)) r=mid,flag=1;
            else l=mid+1;
        }
        if(!flag) cout<<-1<<endl;
        else cout<<r<<endl; 
    }
    return 0;
}