863E - Turn Off The TV - CodeForces Solution

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define mii map<int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define int long long
#define float long double
#define ii pair<int,int>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rloop(i,a,b) for(int i=a;i>b;i--)
#define tr(it,c) for(decltype((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define ft first
#define sd second
#define mod11 998244353ll
#define MOD 1000000007ll
#define mem(a,b) memset(a,b, sizeof(a))
#define SYNC ios_base::sync_with_stdio(false);cin.tie(NULL)
#define PI 3.1415926535
#define ll long long
#define pq priority_queue
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif
 
// typedef long long int;
 
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; 
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; 
 
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
// void _print(pbds v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
 
/*---------------------------------------------------------------------------------------------------------------------------*/
int gcd(int a, int b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(int a, int b, int*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); int x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
int mminv(int a, int b) {int arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
int mminvprime(int a, int b) {return expo(a, b - 2, b);}
bool revsort(int a, int b) {return a > b;}
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
int combination(int n, int r, int m, int *fact, int *ifact) {int val1 = fact[n]; int val2 = ifact[n - r]; int val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
void google(int t) {cout << "Case #" << t << ": ";}
vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
int mod_div(int a, int b, int m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
int phin(int n) {int number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (int i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
/*--------------------------------------------------------------------------------------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void deb() {cerr << "\n";}
template <typename T, typename... V> void deb(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; deb(v...);}
// DEBUG FUNCTIONS END
 
 const int mod = 1e9 +7;
 
 
 
 
struct mint {
    int x;
    mint() : x(0) {}
    mint(int x) : x((x % mod + mod) % mod) {}
    mint operator -() const { return mint(0) - *this;}
    mint operator ~() const { return mint(1) / *this;}
    mint& operator +=(const mint& a) { if((x += a.x) >= mod) x -= mod; return *this;}
    mint& operator -=(const mint& a) { if((x += mod - a.x) >= mod) x -= mod; return *this;}
    mint& operator *=(const mint& a) { x = x * a.x % mod; return *this;}
    mint& operator /=(const mint& a) { x = x * a.pow(mod-2).x % mod; return *this;}
    mint operator +(const mint& a) const { return mint(*this) += a;}
    mint operator -(const mint& a) const { return mint(*this) -= a;}
    mint operator *(const mint& a) const { return mint(*this) *= a;}
    mint operator /(const mint& a) const { return mint(*this) /= a;}
    mint pow(int t) const { mint ret(1), pw = mint(*this); while(t){ if(t & 1) ret *= pw; pw *= pw; t /= 2;} return ret;}
    bool operator <(const mint& a) const { return x < a.x;}
    bool operator ==(const mint& a) const { return x == a.x;}
    bool operator !=(const mint& a) const { return x != a.x;}
    friend istream& operator >>(istream& is, mint& p) { return is >> p.x; }
    friend ostream& operator <<(ostream& os, mint p){ return os << p.x; }
};
 
 
// Function to return LCM of two numbers
long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
const int N = 2e6 + 5;
 
mint fact[N], inv_fact[N];
 
void pre(){
 
    fact[0] = 1;
    loop(i,1,N)
        fact[i] = fact[i-1] * i;
 
    inv_fact[N - 1] =  ~fact[N - 1];
    rloop(i,N-2,-1)
        inv_fact[i] = inv_fact[i + 1] * (i + 1);
 
}
 
mint ncr(int x, int y){
	pre();
    if(x < y)
        return 0;
    return fact[x] * inv_fact[y] * inv_fact[x - y];
}
 
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
void decToBinary(int n)
{
    // Size of an integer is assumed to be 32 bits
    for (int i = 0; i <= 6; i++) {
        int k = n >> i;
        if (k & 1)
            cout << "1";
        else
            cout << "0";
    }
}
bool prime(int x)
{
	for (int i = 2; i*i <= x; i++)
		if (x%i == 0)
			return 0;
	return 1;
}
struct segtree{
	int size=1,y=1e9+7;
	vector<int>values;
    int neutral=0,p=0;
    int always=0;
	void init(int n)
	{
		while(size<n)
		{
			size*=2;
		}
		values.assign(2*size,p);
		
	}
	void build(vector<int> &a,int x,int lx,int rx)
	{
		if(rx-lx==1)
		{
			values[x]=a[lx];
			return;
		}
		int mid=(lx+rx)/2;
		build(a,2*x+1,lx,mid);
		build(a,2*x+2,mid,rx);
		values[x]=max(values[2*x+1],values[2*x+2]);
		return;
	}
	void build(vi &a)
	{
		build(a,0,0,size);
	}
/*	void set(int a,int l,int x,int lx,int rx)
	{
	    
	    if(rx-lx==1)
		{
			values[x]+=a;
			return;
		}
		int mid=(lx+rx)/2;
		if(l<mid)
		{
			set(a,l,2*x+1,lx,mid);
		}
		else
		{ 
		    set(a,l,2*x+2,mid,rx);
		}
		values[x]=values[2*x+1]+values[2*x+2];
		return;
		
	}
	void set(int l,int v)
	{
		set(v,l,0,0,size);
	}*/
	int query(int l,int r,int x, int lx,int rx)
	{
	   if(l>=rx||lx>=r)return 0;
	   if(lx>=l&&rx<=r)
	   {
	   return values[x];
	   }
	   int mid=(lx+rx)/2;
	   int a3=query(l,r,2*x+1,lx,mid);
	   int a4=query(l,r,2*x+2,mid,rx);
	   return max(a3,a4);
	}
	int query(int l,int r)
	{
		return query(l,r,0,0,size);
		
	}
};
void solve()
{
 mii m1,m2,m3,m4,m5,m6;
 int n;cin>>n;
 vii v1,v2;
 loop(i,0,n)
 {
 	int x,y;cin>>x>>y;
 	v1.pb({x,y});
 	v2.pb({y,x});
 	if(m1.find(x)==m1.end())
 	{
 		m1[x]=1;
 		m2[x]=i;
 		m5[x]=y;
	}
	else
	{
		m1[x]++;
		if(m5[x]>y)
		{
			m5[x]=y;
			m2[x]=i;
		}
	}
 	if(m3.find(y)==m3.end())
 	{
 		m3[y]=1;
 		m4[y]=i;
 		m6[y]=x;
	}
	else
	{
		m3[y]++;
		if(m6[y]<x)
		{
			m6[y]=x;
			m4[y]=i;
		}
	}
 //	cout<<i<<endl;
 }
 //cout<<"a";
 tr(it,m1)
 {
 	if(it->sd>1)
 	{
 		cout<<m2[it->ft]+1;return;
	}
 }
 tr(it,m3)
 {
 	if(it->sd>1)
 	{
 		cout<<m4[it->ft]+1;return;
	}
 }
 sort(v1.begin(),v1.end());
 sort(v2.begin(),v2.end());
 vi v3(n,0),v4(n,1e9+9);
 v3[0]=v1[0].sd;
 v4[n-1]=v2[n-1].sd;
 loop(i,1,n)
 {
 	v3[i]=max(v1[i].sd,v3[i-1]);
 }
 rloop(i,n-2,-1)
 {
 	v4[i]=min(v4[i+1],v2[i].sd);
 }
 vi vx;
 loop(i,0,n)
 {
 	vx.pb(v2[i].ft);
 }
/* loop(i,0,n)
 {
 	cout<<v3[i]<<" ";
 }
 cout<<endl;
 loop(i,0,n)
 {
 	cout<<v4[i]<<" ";
 }
 cout<<endl;*/
 loop(i,1,n)
 {
 	int x=v1[i].ft,y=v1[i].sd;
 	//cout<<x<<" "<<y<<endl;
 	int z=lower_bound(vx.begin(),vx.end(),y+1)-vx.begin();
 	if(z==n)continue;
 	int mx1=v3[i-1];
 	int mx2=v4[z];
 	//cout<<mx1<<" "<<mx2<<endl;
 	if(mx1-mx2>=-1)
 	{
 		cout<<m2[x]+1;return;
	}
 }
 cout<<-1;
}
signed main()
{
 
 
	SYNC;
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
 
 
	int t1=1;
//	cin>>t1;
	loop(i1,1,t1+1)
	{

		//cout<<"Case #"<<i<<": ";
		/*if(i1!=254)solve();
		else
		{
			int n,k,x;
			cin>>n>>k>>x;
			cout<<n<<"."<<k<<"."<<x;
		}*/
		solve();
		cout<<"\n";
	}
	return 0;
}