You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

在警方调查中，已经确定了 $n$ 个嫌疑人，现在就靠目击者找到犯罪者了。现已测量出每个嫌疑人 $i$ 的身高，但是由于测量的不可靠性，所以他们的身高是一个从 $l_i$ 到 $r_i$ 范围内的实数（包括两端）。最多一个嫌疑人是犯罪者，并且存在他们都不是犯罪者的情况。

对于一次排队，首先要选择两个正整数 $a$ 和 $b$，其中 $1\le a\le b\le n$，然后把嫌疑人 $a,a+1,\ldots,b$ 带到另一个房间，让目击者可以认出犯罪人。因为如果有两个嫌疑人身高相同的话，目击者可能会有疑惑，所以只有在有可能保证没有两个嫌疑人的身高相同的时候，才能进行一次排队。在一次排队的过程中，如果犯罪人在选出的嫌疑人中，目击者总可以分辨出来，或者他们可以分辨出犯罪人不在这些嫌疑人中。

警方的首席调查员目前对这样形式的问题感兴趣：「如果我能确定犯罪人的编号只能在 $p$ 到 $q$ 之间（$p\le q$），那么在最差情况下，需要多少次排队才能让目击者找出犯罪人，或者报告犯罪人不在嫌疑人中？」请帮助首席调查员回答 $q$ 个这样的问题。

输入格式

第一行包含一个正整数 $n$，表示嫌疑人数。

接下来 $n$ 行，每行两个正整数 $l_i$ 和 $r_i\ (1\le l_i\le r_i\le 10^9)$，表示编号为 $i$ 的嫌疑人身高范围。

接下来一行包含一个正整数 $q$，表示问题个数。

接下来 $q$ 行，每行两个正整数 $p_i$ 和 $q_i\ (1\le p_i\le q_i\le n)$，表示一个问题。

输出格式

输出 $q$ 行，每一行输出对应问题的答案：最少需要多少次排队。

2
1 1
1 1
3
1 1
2 2
1 2

1
1
2

3
1 1
2 2
3 3
3
1 1
2 3
1 3

1
1
1

5
1 3
3 3
4 6
2 3
1 1
3
1 4
3 5
1 5

3
1
3

对于第一个和第三个问题，只需要三次排队就可以：第一次包含嫌疑人 $1$，第二次包含嫌疑人 $2$ 和 $3$，第三次包含嫌疑人 $4$ 和 $5$。

对于第二个问题，只需要一次排队，包含嫌疑人 $3,4$ 和 $5$ 就可以。

数据范围

对于所有子任务，保证 $1\le n,q\le 200\ 000$。