На координатной прямой задано n отрезков, i-ый отрезок начинается в позиции li и заканчивается в позиции ri. Будем обозначать такой отрезок через [li, ri].
Вы предположили, что один из заданных отрезков покрывает все остальные. Другими словами, существует такой отрезок из заданного набора, в котором содержатся все остальные. Теперь вы хотите убедиться в своем предположении. Найдите отрезок из набора, который покрывает все остальные заданные отрезки, и выведите его номер. Если такого отрезка не существует, выведите -1.
Формально будем считать, что отрезок [a, b] покрывает отрезок [c, d], если выполняется условие a ≤ c ≤ d ≤ b.
Выходные данные
Выведите единственное целое число — номер отрезка, который покрывает все остальные отрезки набора. Если решения не существует, выведите -1.
Отрезки нумеруются с 1 в порядке их появления во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1
2 2
3 3
|
-1
|
|
2
|
6
1 5
2 3
1 10
7 10
7 7
10 10
|
3
|