시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)47318512347.308%

문제

구간 $[l,r]$이란, $l$ 이상 $r$ 이하의 모든 실수로 이루어진 집합을 의미한다.

구간 $N$개가 주어진다. 이때, 다음과 같은 질의 $Q$개를 해결하는 프로그램을 작성하시오.

  • 주어진 $l$과 $r$에 대해, 구간을 $1$개 이상 선택하여 그 교집합이 정확히 $[l,r]$이 되도록 할 수 있는가? 만약 가능하다면, 최소 몇 개의 구간을 선택해야 하는가?

입력

첫 번째 줄에는 구간의 개수 $N$이 주어진다. $(1\leq N\leq 300\, 000)$

그 다음 줄부터 $N$개의 줄에 걸쳐, 한 줄에 하나씩 구간 $[l_i,r_i]$를 나타내는 정수 $l_i$와 $r_i$가 공백으로 구분되어 주어진다. $(0\leq l_i<r_i\leq 10^6)$

그 다음 줄에는 질의의 개수 $Q$가 주어진다. $(1\leq Q\leq 300\, 000)$

그 다음 줄부터 $Q$개의 줄에 걸쳐, 한 줄에 하나씩 질의에서 주어지는 두 정수 $l$과 $r$이 공백으로 구분되어 주어진다. $(0\leq l<r\leq 10^6)$

출력

각 질의마다 한 줄에 하나씩, 구간의 교집합이 정확히 $[l,r]$이 되도록 할 수 없으면 $-1$을 출력하고, 할 수 있으면 선택해야 하는 구간의 최소 개수를 출력한다.

예제 입력 1

3
0 10
2 6
4 8
3
4 6
2 8
1 9

예제 출력 1

2
-1
-1