태양계

한 태양계의 행성들이 여러 개의 매우 복잡한 관세 동맹을 맺었다. 각 관세 동맹은 연속된 구간의 행성들로 이루어지며, 관세 동맹 $[a, b]$은 태양에서부터 세었을 때 $a$번째 행성과 $b$번째 행성 사이의 모든 행성으로 이루어진다.

당신의 친구 Zorgax는 행성 간 운송을 담당하는 대형 물류 회사를 운영한다. 회사가 두 행성 사이에서 운송할 때마다, 두 행성 사이에서 진입하거나 이탈하는 각 관세 동맹에 대해 통관 절차를 거쳐야 한다. 하지만 어떤 관세 동맹이 여정의 출발점과 도착점 사이에 엄격히 놓여 있다면, 운송 과정에서 그 관세 동맹의 통관 절차를 거칠 필요가 없다. 그 동맹에 속한 모든 행성 위를 단순히 날아가기 때문이다.

각 운송에 앞서 Zorgax는 운송 과정에서 어떤 진입 및 이탈 통관 절차를 거쳐야 하는지 먼저 알아내야 한다. 이는 시간이 매우 오래 걸리므로, Zorgax는 당신에게 도움을 요청했다.

Zorgax는 서로 다른 $Q$개의 여정을 계획했으며, 각 여정은 두 행성 사이를 이동한다. 계획된 각 여정에 대해 운송 과정에서 거쳐야 하는 진입 및 이탈 통관 절차의 수를 출력한다.

채점

당신의 풀이는 각각 일정한 점수가 배정된 테스트 그룹들로 평가된다. 각 테스트 그룹에는 여러 테스트 케이스가 들어 있다. 한 테스트 그룹의 점수를 얻으려면 해당 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$15$| $Q=1$

$2$ |$35$| 모든 $i$에 대해 $l_i \le l_{i + 1}$이고 $r_i \le r_{i+1}$이다.

$3$ |$38$| $a,b,r_i \leq 10^5$

$4$ |$12$| 추가 제한 조건이 없다.

첫째 줄에 관세 동맹의 수 $N$ ($1 \le N \le 10^5$)이 주어진다.

이어서 각 관세 동맹마다 한 줄씩, $N$개의 줄이 주어진다. 이 중 $i$번째 줄에는 두 정수 $1 \le l_i \leq r_i \le 10^9$가 주어진다. 이는 행성들이 태양으로부터의 거리에 따라 번호가 매겨졌을 때, $l_i \leq j \leq r_i$를 만족하는 모든 행성 $j$로 이루어진 관세 동맹이 있다는 뜻이다.

다음 줄에는 계획된 여정의 수 $Q$ ($1 \le Q \le 10^5$)가 주어진다.

마지막으로 각 여정마다 한 줄씩, $Q$개의 줄이 주어진다. 각 줄에는 두 정수 $1 \le a \neq b \le 10^9$가 주어지며, 각각 여정이 출발하는 행성과 도착하는 행성을 나타낸다.

각 여정마다 운송 과정에서 거쳐야 하는 진입 및 이탈 통관 절차의 수를 나타내는 정수 하나를 출력한다.

예제 케이스 $2$에는 다섯 개의 관세 동맹이 있다. 이 중 행성 $1$은 첫 번째와 네 번째 동맹에 속하고, 행성 $10$은 첫 번째와 다섯 번째 동맹에 속한다. 따라서 행성 $1$과 $10$ 사이의 여정에는 두 번의 통관 절차가 필요하다. 첫 번째는 운송 수단이 행성 $1$과 네 번째 동맹을 떠날 때이고, 다른 한 번은 행성 $10$에 도착하여 다섯 번째 동맹에 진입할 때이다. 두 번째와 세 번째 동맹은 두 행성 사이에 엄격히 놓여 있으므로, 운송 수단은 이 두 동맹 중 어느 곳에도 진입할 필요가 없다. 따라서 답은 $2$이다.