← 返回题目列表

Codeforces · 863/E

E. 关闭电视

中文机器翻译题面 查看原题

卢巴再次需要你的帮助! Luba有n台电视机。她知道第 i 台电视机将从时间 li 到时间 ri(包括时间 ri)工作。

Luba 想要关闭其中一台电视机以释放插座。如果某台电视机在关闭后至少一台电视机正在工作的整数时刻的数量不会减少,我们就称其为冗余电视机。如果卢巴不得不关掉一台非冗余的电视机,她会非常不高兴。

帮助 Luba,告诉她一些多余电视机的索引。如果没有,则打印-1。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — 电视机的数量。

接下来n行,每行包含两个整数li, ri (0 ≤ li ≤ ri ≤ 109),表示第i台电视机的工作时间。

输出

如果没有多余的电视机,则打印-1。否则打印任何冗余电视机的索引(电视机索引从 1 到 n)。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
1 3
4 6
1 7

输出 #1

1

输入 #2

2
0 10
0 10

输出 #2

1

输入 #3

3
1 2
3 4
6 8

输出 #3

-1

输入#4

3
1 2
2 3
3 4

输出#4

2

注意

考虑第一个样本。最初,至少一台电视机正在工作的所有整数时刻都来自段[1;7]。很容易看出,如果我们关闭第一台电视机(或第二台),该片段不会改变。

请注意,在第四个示例中,您可以关闭第二台电视机,因为即使没有它,任何电视机正在工作的所有整数时刻都表示段 [1;4]。