一条坐标线有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