A coordinate line has n segments, the i-th segment starts at the position l_{i} and ends at the position r_{i}. We will denote such a segment as [l_{i}, r_{i}].

You have suggested that one of the defined segments covers all others. In other words, there is such segment in the given set, which contains all other ones. Now you want to test your assumption. Find in the given set the segment which covers all other segments, and print its number. If such a segment doesn't exist, print -1.

Formally we will assume that segment [a, b] covers segment [c, d], if they meet this condition a ≤ c ≤ d ≤ b. 


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of segments. Next n lines contain the descriptions of the segments. The i-th line contains two space-separated integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 10^9) — the borders of the i-th segment.

It is guaranteed that no two segments coincide.


-----Output-----

Print a single integer — the number of the segment that covers all other segments in the set. If there's no solution, print -1.

The segments are numbered starting from 1 in the order in which they appear in the input.


-----Examples-----
Input
3
1 1
2 2
3 3

Output
-1

Input
6
1 5
2 3
1 10
7 10
7 7
10 10

Output
3

Difficulty: interview

Starter code:

Solutions:
#python33
def program():
    num=-1
    R=[]
    L=[]
    n=int (eval(input ()))
    for i in range(n):
        l,r=((list(map(int,input().split()))))  
        R.append(r)
        L.append(l)  
    MAXR=max(R)
    MINL=min(L)

    for i in range(n):
        if R[i] == MAXR and L[i] == MINL:
            print(i+1)
            return 

    print(num)    
program()       


import sys
f = sys.stdin
#f = open("input.txt", "r")
n = int(f.readline().strip())
l, r = [], []
for line in f:
    l.append(int(line.strip().split()[0]))
    r.append(int(line.strip().split()[1]))
ls = list(set(l))
rs = list(set(r))
ls.sort(); rs.sort(reverse=True)
ind = -1
for i in range(n):
    if l[i] <= ls[0] and r[i] >= rs[0]:
        ind = i+1
print(ind)

n=int(input())
ans=0
a,b=0,0
mina,maxb=list(map(int,input().split()))
for i in range(1,n):
    a,b=list(map(int,input().split()))
    if a<mina:
        mina=a
        ans=-1
    if b>maxb:
        maxb=b
        ans=-1
    if a==mina and b==maxb:
        ans=i
if ans==-1:
    print(ans)
else:
    print(ans+1)

    


A, B, ans = 1000000000, 1, -1
for i in range(1, int(input()) + 1):
    a, b = map(int, input().split())
    if a < A:
        A = a
        ans = -1
    if b > B:
        B = b
        ans = -1
    if a == A and b == B: ans = i
print(ans)

A, B, ans = 1000000000, 1, -1
for i in range(1, int(input()) + 1):
    a, b = map(int, input().split())
    if a > A:
        if b > B:
            B = b
            ans = -1
    else:
        if b >= B:
            B = b
            ans = i
        elif a != A: ans = -1
        A = a
print(ans)

A, B, ans = 1000000000, 1, -1
for i in range(1, int(input()) + 1):
    a, b = map(int, input().split())
    if a > A:
        if b > B: B, ans = b, -1
    else:
        if b >= B: A, B, ans = a, b, i
        elif a != A: A, ans = a, -1
print(ans)

def Q(x):
    return x[1]-x[0]+1
n=int(input())
L=[]
for i in range(n):
    x,y=list(map(int,input().split()))
    L.append((x,y,i+1))

L.sort(key=Q,reverse=True)
ans=L[0][2]
for i in range(1,n):
    if(L[i][0]>=L[0][0] and L[i][1]<=L[0][1]):
        continue
    ans=-1
print(ans)


vl, vr, vi, maxr = 1000000001, 0, 0, 0
for i in range(1, int(input()) + 1):
    l, r = (int(x) for x in input().split())
    if l < vl or (l == vl and r > vr):
        vl, vr, vi = l, r, i
    maxr = max(maxr, r)
print(vi if vr >= maxr else -1)

import sys
import math

n = int(sys.stdin.readline())
d = []

vmin = 1000000001
vmax = 0

for i in range(n):
    l, r = [int(x) for x in (sys.stdin.readline()).split()]
    d.append((i + 1, (l, r)))
    if(l < vmin):
        vmin = l
    if(r > vmax):
        vmax = r
        
d.sort(key = lambda x: x[1][0])   

k = -1
for i in d:
    if(i[1][0] <= vmin):
        if(i[1][1] >= vmax):
            k = i[0]
    else:
        break

print(k)    


import sys
import math

n = int(sys.stdin.readline())
d = []

vmin = 1000000001
vmax = 0

for i in range(n):
    l, r = [int(x) for x in (sys.stdin.readline()).split()]
    d.append((i + 1, (l, r)))
    if(l < vmin):
        vmin = l
    if(r > vmax):
        vmax = r
        
#d.sort(key = lambda x: x[1][0])   

k = -1
for i in d:
    if(i[1][0] <= vmin and i[1][1] >= vmax):
        k = i[0]

print(k)    


n = int(input())
l = []
best = [0, -1]
k = -1
for i in range(n):
	l.append([int(x) for x in input().split()])
	if l[-1][1] - l[-1][0] > best[1] - best[0]:
		best = l[-1]
		k = i
for a, b in l:
	if a < best[0] or best[1] < b:
		print(-1)
		return
print(k + 1)


def main():
    n = int(input())
    mi, ma = 10000000001, 0
    l = []
    for _ in range(n):
        a, b = map(int, input().split())
        if mi > a:
            mi = a
        if ma < b:
            ma = b
        l.append((a, b))
    l.append((mi, ma))
    idx = l.index((mi, ma))
    print(-1 if idx == n else idx + 1)


def __starting_point():
    main()
__starting_point()

def main():
    n = int(input())
    l, r = [], []
    for _ in range(n):
        a, b = map(int, input().split())
        l.append(a)
        r.append(b)
    l.append(min(l))
    r.append(max(r))
    l = list(zip(l, r))
    idx = l.index(l[-1])
    print(-1 if idx == n else idx + 1)


def __starting_point():
    main()
__starting_point()

def main():
    n = int(input())
    l, r = [], []
    for _ in range(n):
        a, b = map(int, input().split())
        l.append(a)
        r.append(b)
    m = min(l), max(r)
    for i, a in enumerate(zip(l, r)):
        if a == m:
            print(i + 1)
            return
    print(-1)


def __starting_point():
    main()
__starting_point()

maxx = -1
minn = 10**10
bad = []
a = int(input())
for i in range(a):
    x, y = list(map(int, input().split(' ')))
    bad.append([x, y])
    maxx = max(maxx, y)
    minn = min(minn, x)

for i in range(a):
    if bad[i][0] <= minn <= maxx <= bad[i][1]:
        print(i+1)
        quit()
print(-1)


num = int(input())
l = []
k = []
mi = 100000000000
ma = 0
for i in range(num):
	a,b = input().split()
	a = int(a)
	b = int(b)
	if a < mi:
		mi = a
	if b > ma:
		ma = b
	l.append((a,b))
if (mi,ma) in l:
	print(l.index((mi,ma))+1)
else:
	print('-1')

# coding: utf-8
n = int(input())
segments = [[int(i) for i in input().split()] for j in range(n)]
left = segments[0][0]
right = segments[0][1]
for seg in segments:
    if seg[0]<left:
        left = seg[0]
    if seg[1]>right:
        right = seg[1]
for i in range(n):
    if segments[i][0]<=left and segments[i][1]>=right:
        print(i+1)
        break
else:
    print(-1)


n = int(input())
segments = [list(map(int, (input() + " " + str(i + 1)).split())) for i in range(n)]
ssegments = sorted(segments, key = lambda seg: seg[1], reverse = True)
ssegments = sorted(ssegments, key = lambda seg: seg[0])

good = True
for s in ssegments:
    if ssegments[0][0] > s[0] or ssegments[0][1] < s[1]:
        good = False
        break

if good:
    print(ssegments[0][2])
else:
    print(-1)



from collections import defaultdict, deque, Counter, OrderedDict

def main():
    n = int(input())
    mi,ma = 10**10,-1
    l = []
    for i in range(n):
        a,b = map(int,input().split())
        mi = min(mi,a)
        ma = max(ma,b)
        l.append((a,b))

    check,ind = False,0
    for i,v in enumerate(l):
        if check: break
        check |= (v[0] <= mi and v[1] >= ma)
        ind = i+1

    print(ind if check else -1)


def __starting_point():
    """sys.setrecursionlimit(400000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()"""
    main()
__starting_point()

n = int(input())
ret = -1
left = []
right = []

for i in range(n):
	a, b = map(int, input().split(" "))
	left.append(a)
	right.append(b)
ml = left[0]
mr = right[0]
for i in range(n):
	if(left[i] < ml):
		ml = left[i]
	if(right[i] > mr):
		mr = right[i]
for i in range(n):
	if(left[i] <= ml and mr <= right[i]):
		ret = i+1
print(ret)

R=input
I=lambda:map(int,R().split())
n=int(R())
a=[]
b=[]
for i in range(n):x,y=I();a.append(x);b.append(y)
x=min(a)
y=max(b)
for i in range(n):
	if a[i]==x and b[i]==y:print(i+1);return
print(-1)

n=int(input())
l=[]
mi,ma=11**11,0
for _ in range(n):
    x,y=map(int,input().split())
    if x<mi: mi=x
    if y>ma: ma=y
    l+=[(x,y)]
if (mi,ma) in l: print(l.index((mi,ma))+1)
else: print(-1)

n=int(input())
v1,v2=[],[]
for i in range(n):
	a,b=map(int,input().split(' '))
	v1.append(a)
	v2.append(b)
a,b=min(v1),max(v2)
t=0
for i in range(n):
	if(v1[i]<=a and v2[i]>=b):
		print(i+1)
		t=1
		break
if(t==0):
	print(-1)

n = int(input())

minn, maxn = (int(i) for i in input().split())
numbers = {(minn, maxn):0}

for j in range(1, n):
    a, b = (int(i) for i in input().split())
    numbers[(a,b)] = j 

    if b > maxn: maxn = b
    if a < minn: minn = a

if (minn, maxn) in numbers:
    print(numbers[(minn, maxn)] + 1)
else:
    print(-1)


n = int(input())

L = []
R = []
pair = []
for i in range(n):
	l, r = input().split()
	L.append(int(l))
	R.append(int(r))
	pair.append(l + '-'+ r)

minL = min(L)
maxR = max(R)

if (str(minL) + '-' + str(maxR)) in pair:
	print(pair.index(str(minL) + '-' + str(maxR)) + 1)
else:
	print(-1)