치터 찾기

면접 대비

시간 제한2초메모리 제한1024 MB

요약

연속된 구간 [l, r]을 찾습니다. 치터의 주장 구간은 [l, r]과 겹치지 않고, 치터가 아닌 피돌의 주장 구간은 [l, r]과 겹쳐야 합니다.

난이도: 보통10점 중 6점
유형: 투 포인터, 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

피돌이 $N$ 명에게 $1$ 부터 $N$ 까지의 서로 다른 번호가 매겨져 있다. 이 중 치터가 몇 명 섞여 있고, 치터들의 번호는 연속한다. 구체적으로, 어떤 두 정수 $l$ , $r$ $(1 \leq l \leq r \leq N)$ 에 대해 $l$ 번 피돌이부터 $r$ 번 피돌이가 모두 치터이고, 나머지는 모두 치터가 아니다.

$i$ 번 피돌이는 $a_i$ 번 이상 $b_i$ 번 이하의 번호가 매겨진 피돌이 중에 치터가 한 명 이상 있다고 주장한다. $i$ 번 피돌이가 치터가 아니라면 이 주장은 참이다. 하지만 치터 피돌이들은 모두 거짓말을 한다. 즉 $i$ 번 피돌이가 치터라면 $a_i$ 번 이상 $b_i$ 번 이하의 피돌이 중에 치터는 한 명도 없다.

입력

첫째 줄에 피돌이의 수 $N$ 이 주어진다. $(2 \leq N \leq 200\ 000)$

다음 $N$ 개의 줄 중 $i+1$ 번째 줄에는 $i$ 번 피돌이의 주장을 나타내는 두 정수 $a_i$ , $b_i$ 가 공백으로 구분되어 주어진다. 이는 $i$ 번 피돌이가 $a_i$ 번 이상 $b_i$ 번 이하의 피돌이 중에 치터가 한 명 이상 있다고 주장했음을 뜻한다. $(1 \leq a_i \leq b_i \leq N)$

출력

가능한 $l$ , $r$ 을 공백으로 구분해 한 줄에 출력한다. 가능한 답이 여러 개라면 그중 아무거나 하나를 출력한다.

예제1

예제 1
입력
```
6
3 4
4 5
1 1
1 4
1 2
2 6
```
예상 출력
```
2 3
```