#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast")
 
#define ll long long
// #define int ll
#define all(v) v.begin(),v.end()
#define sz(s) ((int)s.size())
#define pb push_back
// #define F first
// #define S second
// #define pii pair<int,int>
// #define ppb pop_back
#define lb lower_bound
#define ub upper_bound

using namespace std;
 
const int inf=1e8;
const int MAX=3e5+10;
const int mod=1e9+7;
 
int binpow(int a,int n){
    if(!n)return 1;
    if(n%2==1)return a*binpow(a,n-1)%mod;
    int k=binpow(a,n/2);
    return k*k%mod;
}
 
int n,k,q,m;
int a[MAX],b[MAX],x[MAX],t[MAX];
int l[MAX],y[MAX];
vector<int> events[MAX+MAX+MAX],zap[MAX+MAX+MAX];
multiset<int> st[MAX];
vector<int> tim,pos;
 
struct segtree{
    multiset<int> t[2*2*MAX];
    int mx[2*2*MAX];
 
    segtree(){
        memset(mx,-1,sizeof(mx));
    }
 
    void add(int v,int tl,int tr,int pos,int x){
        pos+=m;
        t[pos].insert(x);
        mx[pos]=*t[pos].rbegin();
        while(pos>1){
            pos/=2;
            mx[pos]=max(mx[2*pos],mx[2*pos+1]);
        }
    }
 
    void del(int v,int tl,int tr,int pos,int x){
        pos+=m;
        t[pos].erase(t[pos].find(x));
        mx[pos]=(t[pos].empty()?-1:*t[pos].rbegin());
        while(pos>1){
            pos/=2;
            mx[pos]=max(mx[2*pos],mx[2*pos+1]);
        }
    }
 
    int get(int v,int tl,int tr,int l,int r){
        l+=m,r+=m+1;
        int res=0;
        while(l<r){
            if(l&1){
                res=max(res,mx[l++]);
            }
            if(r&1){
                res=max(res,mx[--r]);
            }
            l/=2,r/=2;
        }
        return res;
    }
}tree;
 
int cnt[MAX],col;
 
int getx(int x){
    return lb(all(pos),x)-pos.begin();
}
 
void add(int id){
    if(cnt[t[id]]==0)col++;
    cnt[t[id]]++;
    if(st[t[id]].find(x[id])!=st[t[id]].end())st[t[id]].insert(x[id]);
    else{
        auto l=--st[t[id]].lb(x[id]);
        auto r=l;
        r++;
        int LL=getx(*l+1);
        if(!(*l==-1&&*r==inf+1))tree.del(1,0,m-1,LL,*r-1);
        tree.add(1,0,m-1,LL,x[id]-1);
        tree.add(1,0,m-1,getx(x[id]+1),*r-1);
        st[t[id]].insert(x[id]);
    }
}
 
void del(int id){
    id=-id;
    cnt[t[id]]--;
    if(cnt[t[id]]==0)col--;
    st[t[id]].erase(st[t[id]].find(x[id]));
    if(st[t[id]].find(x[id])==st[t[id]].end()){
        auto l=--st[t[id]].lb(x[id]);
        auto r=l;
        r++;
        int LL=getx(*l+1);
        tree.del(1,0,m-1,LL,x[id]-1);
        tree.del(1,0,m-1,getx(x[id]+1),*r-1);
        if(!(*l==-1&&*r==inf+1))tree.add(1,0,m-1,LL,*r-1);
    }
}
 
bool check(int l,int r){
    l=max(l,0);
    r=min(r,inf);
    l=ub(all(pos),l)-pos.begin()-1;
    if(tree.get(1,0,m-1,0,l)>=r)return 0;
    return 1;
}
 
int ans[MAX];
 
void solve(){
    
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}