← 返回题目列表

Codeforces · 976/C

C. 嵌套段

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

给定一个序列 a1, a2, ..., an,由编号为 1 到 n 的一维段组成。您的任务是找到两个不同的索引 i 和 j,使得段 ai 位于段 aj 内。

段 [l1, r1] 位于段 [l2, r2] 内,当且仅当 l1 ≥ l2 且 r1 ≤ r2。

打印索引 i 和 j。如果有多个答案,请打印其中任何一个。如果不存在答案,则打印 -1 -1。

输入

第一行包含一个整数 n (1 ≤ n ≤ 3·105) — 段数。

接下来的 n 行中的每一行都包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ 109) — 第 i 段。

输出

打印两个不同的索引 i 和 j,使得段 ai 位于段 aj 内。如果有多个答案,请打印其中任何一个。如果不存在答案,则打印 -1 -1。

示例

输入 #1

5
1 10
2 9
3 9
2 3
2 9

输出 #1

2 1

输入 #2

3
1 5
2 6
6 20

输出 #2

-1 -1

注意

在第一个示例中,以下对被认为是正确的:

- (2, 1), (3, 1), (4, 1), (5, 1) — 甚至不接触边界;
- (3, 2), (4, 2), (3, 5), (4, 5) — 触摸一个边框;
- (5, 2), (2, 5) — 完全匹配。