Luba needs your help again! Luba has n TV sets. She knows that i-th TV set will be working from moment of time li till moment ri, inclusive.

Luba wants to switch off one of TV sets in order to free the socket. Let's call some TV set redundant if after switching it off the number of integer moments of time when at least one of TV sets is working won't decrease. Luba will be very upset if she has to switch off a non-redundant TV set.

Help Luba by telling her the index of some redundant TV set. If there is no any, print -1.

Input

The first line contains one integer number n (1 ≤ n ≤ 2·105) — the number of TV sets.

Then n lines follow, each of them containing two integer numbers li, ri (0 ≤ li ≤ ri ≤ 109) denoting the working time of i-th TV set.

Output

If there is no any redundant TV set, print -1. Otherwise print the index of any redundant TV set (TV sets are indexed from 1 to n).

If there are multiple answers, print any of them.

Examples

Input

3
1 3
4 6
1 7


Output

1


Input

2
0 10
0 10


Output

1


Input

3
1 2
3 4
6 8


Output

-1


Input

3
1 2
2 3
3 4


Output

2

Note

Consider the first sample. Initially all integer moments of time such that at least one TV set is working are from the segment [1;7]. It's easy to see that this segment won't change if we switch off the first TV set (or the second one).

Note that in the fourth sample you can switch off the second TV set, since even without it all integer moments such that any of the TV sets is working denote the segment [1;4].
import java.util.*;
import java.io.*;
import java.math.*;
public class code7 {
	InputStream is;
	PrintWriter out;
	static long mod=pow(10,9)+7;
	int dx[]= {0,0,1,-1},dy[]={+1,-1,0,0};
	void solve()
	{
		int n=ni();
		Pair p[]=new Pair[n];
		for(int i=0;i<n;i++)
			p[i]=new Pair(ni(),ni(),-1);
		int arr[]=new int[6*n];
		int index=0;
		for(int i=0;i<n;i++)
		{
			arr[index++]=p[i].x-1;
			arr[index++]=p[i].x;
			arr[index++]=p[i].x+1;
			arr[index++]=p[i].y;
			arr[index++]=p[i].y-1;
			arr[index++]=p[i].y+1;
		}
		Arrays.sort(arr);
		HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
		index=0;
		hm.put(arr[0],index++);
		for(int i=1;i<arr.length;i++)
		{
			if(arr[i]!=arr[i-1])
				hm.put(arr[i],index++);
		}
		segtree st=new segtree(index);
		for(int i=0;i<n;i++)
		{
			int l=hm.get(p[i].x);
			int r=hm.get(p[i].y);
			st.update(l,r,+1);
		}
		int ans=-2;
		for(int i=0;i<n;i++)
		{
			int l=hm.get(p[i].x);
			int r=hm.get(p[i].y);
			int min=st.rangeq(l,r);
			if(min!=Integer.MAX_VALUE&&min>1)
			{
				ans=i;
				break;
			}
		}
		out.println(ans+1);
	}
	static class segtree{
		int arr[], st[], size,lazy[];
		segtree(int a[]){
			arr = a.clone();
			size = arr.length-1;
			st = new int[4*(size+1)+1];
			lazy=new int[4*(size+1)+1];
			build(0,0,size);
		}
		segtree(int size)
		{
			this.size=size;
			st=new int[4*(size+1)+1];
			lazy=new int[4*(size+1)+1];
		}
		int merge(int a,int b)
		{
			return Math.min(a,b);
		}
		void build(int n, int l, int r){
			if(l==r){
				st[n] = arr[l];
				return;
			}
			int mid = (l+r)/2;
			build(2*n+1,l,mid); build(2*n+2,mid+1,r);				
			st[n]=merge(st[2*n+1], st[2*n+2]);
		}
		int get(int ql,int qr)
		{
			return get(0,0,size,ql,qr);
		}
		int get(int n,int l,int r,int ql,int qr){
			if(ql>r || qr<l || l>r) return 0;
			if(ql<=l&&qr>=r) return st[n];
			int mid = (l+r)/2;
			return merge(get(2*n+1,l,mid,ql,qr), get(2*n+2,mid+1,r,ql,qr));
		}
		void update(int index,int dx)
		{
			update(0,0,size,index,dx);
		}
		void update(int n,int l,int r,int index,int dx)
		{
			if(l==r)
			{
				st[n]+=dx;
				arr[l]+=dx;
				return;
			}
			int mid=(l+r)/2;
			if(index<=mid)
				update(2*n+1,l,mid,index,dx);	
			else
				update(2*n+2,mid+1,r,index,dx);
			st[n]=merge(st[2*n+1],st[2*n+2]);
		}
		void update(int ul,int ur,int dx)
		{
			update(0,0,size,ul,ur,dx);
		}
		void update(int n,int l,int r,int ul,int ur,int dx)
		{
			if(lazy[n]!=0)
			{
				st[n]+=lazy[n];
				if(l!=r)
				{
					lazy[2*n+1]+=lazy[n];
					lazy[2*n+2]+=lazy[n];
				}
				lazy[n]=0;
			}
			if(ul>r||ur<l)
				return;
			if(ul<=l&&ur>=r)
			{
				st[n]+=dx;
				if(l!=r)
				{
					lazy[2*n+1]+=dx;
					lazy[2*n+2]+=dx;
				}
				return;
			}
			int mid=(l+r)/2;
			update(2*n+1,l,mid,ul,ur,dx);
			update(2*n+2,mid+1,r,ul,ur,dx);
			st[n]=merge(st[2*n+1],st[2*n+2]);
		}
		int rangeq(int ql,int qr)
		{
			return rangeq(0,0,size,ql,qr);
		}
		int rangeq(int n,int l,int r,int ql,int qr)
		{
			if(lazy[n]!=0)
			{
				st[n]+=lazy[n];
				if(l!=r)
				{
					lazy[2*n+1]+=lazy[n];
					lazy[2*n+2]+=lazy[n];
				}
				lazy[n]=0;
			}
			if(ql>r||qr<l)
				return Integer.MAX_VALUE;
			if(ql<=l&&qr>=r)
				return st[n];
			int mid=(l+r)/2;
			return merge(rangeq(2*n+1,l,mid,ql,qr),rangeq(2*n+2,mid+1,r,ql,qr));
		}
	}
	public static int count(int x)
	{
		int num=0;
		while(x!=0)
		{
			x=x&(x-1);
			num++;
		}
		return num;
	}
	static long d, x, y;
	void extendedEuclid(long A, long B) {
	    if(B == 0) {
	        d = A;
	        x = 1;
	        y = 0;
	    }
	    else {
	        extendedEuclid(B, A%B);
	        long temp = x;
	        x = y;
	        y = temp - (A/B)*y;
	    }
	}
	long modInverse(long A,long M) //A and M are coprime
	{
	    extendedEuclid(A,M);
	    return (x%M+M)%M;    //x may be negative
	}
	public static void mergeSort(int[] arr, int l ,int r){
		if((r-l)>=1){
			int mid = (l+r)/2;
			mergeSort(arr,l,mid);
			mergeSort(arr,mid+1,r);
			merge(arr,l,r,mid);
		}
	}
	public static void merge(int arr[], int l, int r, int mid){
		int n1 = (mid-l+1), n2 = (r-mid);
		int left[] = new int[n1];
		int right[] = new int[n2];
		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
		int i =0, j =0, k = l;
		while(i<n1 && j<n2){
			if(left[i]>right[j]){
				arr[k++] = right[j++];
			}
			else{
				arr[k++] = left[i++];
			}
		}
		while(i<n1) arr[k++] = left[i++];
		while(j<n2) arr[k++] = right[j++];
	}
	public static void mergeSort(long[] arr, int l ,int r){
		if((r-l)>=1){
			int mid = (l+r)/2;
			mergeSort(arr,l,mid);
			mergeSort(arr,mid+1,r);
			merge(arr,l,r,mid);
		}
	}
	public static void merge(long arr[], int l, int r, int mid){
		int n1 = (mid-l+1), n2 = (r-mid);
		long left[] = new long[n1];
		long right[] = new long[n2];
		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
		int i =0, j =0, k = l;
		while(i<n1 && j<n2){
			if(left[i]>right[j]){
				arr[k++] = right[j++];
			}
			else{
				arr[k++] = left[i++];
			}
		}
		while(i<n1) arr[k++] = left[i++];
		while(j<n2) arr[k++] = right[j++];
	}
	 static class Pair implements Comparable<Pair>{
		 
	       int x,y,k,i;
	        int xx,yy;
		Pair (int x,int y,int k){
			this.x=x;
			this.y=y;
			this.k=k;
		}
	        
		public int compareTo(Pair o) {
			if(this.y!=o.y)
				return this.y-o.y;
			else
				return this.x-o.x;
		}
		public boolean equals(Object o) {
			if (o instanceof Pair) {
				Pair p = (Pair)o;
				return p.x == x && p.y == y;
			}
			return false;
		}
		public int hashCode() {
			System.out.println("x");
			return new Long(x).hashCode()*31 + new Long(y).hashCode() ;
		}
	           
	 
	        @Override
	        public String toString() {
	            return  "("+x + " " + y +" "+k+" "+i+" )";
	        }
	    
	    } 
	    
	    public static boolean isPal(String s){
	        for(int i=0, j=s.length()-1;i<=j;i++,j--){
	                if(s.charAt(i)!=s.charAt(j)) return false;
	        }
	        return true;
	    }
	    public static String rev(String s){
			StringBuilder sb=new StringBuilder(s);
			sb.reverse();
			return sb.toString();
	    }
	    
	    public static long gcd(long x,long y){
		if(x%y==0)
			return y;
		else
			return gcd(y,x%y);
	    }
	    
	    public static int gcd(int x,int y){
	    	if(y==0) 
	    		return x; 
	    	return gcd(y,x%y);
	    }
	    
	    public static long gcdExtended(long a,long b,long[] x){
	        
	        if(a==0){
	            x[0]=0;
	            x[1]=1;
	            return b;
	        }
	        long[] y=new long[2];
	        long gcd=gcdExtended(b%a, a, y);
	        
	        x[0]=y[1]-(b/a)*y[0];
	        x[1]=y[0];
	        
	        return gcd;
	    }
	    
	    public static int abs(int a,int b){
		return (int)Math.abs(a-b);
	    }
	 
	    public static long abs(long a,long b){
		return (long)Math.abs(a-b);
	    }
	    
	    public static int max(int a,int b){
		if(a>b)
			return a;
		else
			return b;
	    }
	 
	    public static int min(int a,int b){
		if(a>b)
			return b;
		else 
			return a;
	    }
	    
	    public static long max(long a,long b){
		if(a>b)
			return a;
		else
			return b;
	    }
	 
	    public static long min(long a,long b){
		if(a>b)
			return b;
		else 
			return a;
	    }
	 
	    public static long pow(long n,long p,long m){
		 long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;
		    if(result>=m)
		    result%=m;
		    p >>=1;
		    n*=n;
		    if(n>=m)
		    n%=m;
		}
		return result;
	    }
	    
	    public static long pow(long n,long p){
		long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;	    
		    p >>=1;
		    n*=n;	    
		}
		return result;
	    }
	    public static void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
	    void run() throws Exception {
			is = System.in;
			out = new PrintWriter(System.out);
			solve();
			out.flush();
		}
	   
	    public static void main(String[] args) throws Exception {
			new Thread(null, new Runnable() {
				public void run() {
					try {
						new code7().run();
					} catch (Exception e) {
						e.printStackTrace();
					}
				}
			}, "1", 1 << 26).start();

		}
	    private byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;
	 
		private int readByte() {
			if (lenbuf == -1)
				throw new InputMismatchException();
			if (ptrbuf >= lenbuf) {
				ptrbuf = 0;
				try {
					lenbuf = is.read(inbuf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return -1;
			}
			return inbuf[ptrbuf++];
		}
	 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
	 
		private int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b));
			return b;
		}
	 
		private double nd() {
			return Double.parseDouble(ns());
		}
	 
		private char nc() {
			return (char) skip();
		}
	 
		private String ns() {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
	 
		private char[] ns(int n) {
			char[] buf = new char[n];
			int b = skip(), p = 0;
			while (p < n && !(isSpaceChar(b))) {
				buf[p++] = (char) b;
				b = readByte();
			}
			return n == p ? buf : Arrays.copyOf(buf, p);
		}
	 
		private char[][] nm(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = ns(m);
			return map;
		}
	 
		private int[] na(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = ni();
			return a;
		}
	 
		private int ni() {
			int num = 0, b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
		private long nl() {
			long num = 0;
			int b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
}