용의자

경찰 수사에서 n명의 용의자가 확인되었고, 이제 목격자들이 범인을 찾아야 한다. 각 용의자 i의 키를 측정했지만 측정이 부정확해서, 키가 구간 $[l_i, r_i]$에 속하는 실수라는 것만 알려져 있다. 범인은 기껏해야 한 명이며, 아무도 범인이 아닐 수도 있다.

하나의 대면은 두 양의 정수 a와 b($1 \le a \le b \le n$)를 골라 용의자 a, a+1, ..., b를 별도의 방으로 데려가 목격자들이 범인을 식별하도록 하는 것이다. 용의자 두 명의 키가 같으면 목격자들이 혼란스러울 수 있으므로, 대면은 두 용의자의 키가 절대 같지 않다고 보장할 수 있을 때에만 허용된다. 대면 중에 목격자들은 범인이 선택된 용의자 중에 있다면 항상 범인을 식별할 수 있고, 범인이 그중에 없다면 그 사실을 알아낼 수 있다.

수사 책임자는 이제 다음과 같은 질문에 답하려 한다. "범인의 번호가 p와 q 사이($p \le q$)에만 있을 수 있다고 확신한다면, 목격자들이 범인을 찾거나 용의자 중에 범인이 없다고 보고할 수 있도록 하는 데 필요한 대면의 최소 횟수는 최악의 경우 얼마인가?" 수사 책임자가 q개의 이런 질문에 답하도록 도와라.

첫째 줄에는 용의자의 수인 양의 정수 n이 주어진다.

다음 n개 줄에는 용의자 i의 가능한 키 범위를 나타내는 두 양의 정수 $l_i$와 $r_i$($1 \le l_i \le r_i \le 10^9$)가 주어진다.

그다음 줄에는 질문의 수인 양의 정수 q가 주어진다.

다음 q개 줄에는 질문을 나타내는 두 양의 정수 $p_i$와 $q_i$($1 \le p_i \le q_i \le n$)가 주어진다.

q개 줄에 각 질문의 답을 출력한다. 답은 필요한 대면의 최소 횟수이다.

모든 부분문제에서 $1 \le n, q \le 200\,000$이다.

세 번째 예제에 대한 설명:

첫 번째 질문과 세 번째 질문에는 대면 세 번이면 충분하다. 하나는 용의자 1로만 이루어지고, 하나는 용의자 2와 3으로 이루어지며, 하나는 용의자 4와 5로 이루어진다.

두 번째 질문에는 용의자 3, 4, 5로 이루어진 대면 한 번이면 충분하다.