← 返回题目列表

Codeforces · 242/B

B. 大段

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

一条坐标线有n段,第i段从位置li开始,到位置ri结束。我们将这样的一段表示为[li,ri]。

您建议定义的分段之一覆盖所有其他分段。换句话说,给定集合中存在这样的段,其中包含所有其他段。现在你想测试你的假设。在给定的集合中查找覆盖所有其他段的段,并打印其编号。如果这样的段不存在,则打印-1。

正式地,我们假设段 [a, b] 覆盖段 [c, d],如果它们满足条件 a ≤ c ≤ d ≤ b。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 段数。接下来的 n 行包含段的描述。第 i 行包含两个空格分隔的整数 li, ri (1 ≤ li ≤ ri ≤ 109) — 第 i 段的边界。

保证没有两个线段重合。

输出

打印单个整数 — 覆盖集合中所有其他段的段号。如果无解,则打印-1。

这些段按照它们在输入中出现的顺序从 1 开始编号。

示例

输入 #1

3
1 1
2 2
3 3

输出 #1

-1

输入 #2

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

输出 #2

3