Problem Description

There are $n$ suspects, each with an uncertain height, known only to be within a certain range $[l_i, r_i]$.

Each investigation can select all suspects within a given range of indices $[a, b]$, requiring that their height ranges do not overlap. If a suspect appears in an investigation, a witness can immediately make a correct judgment.

Given $q$ queries, each providing $p_i, q_i$, determine the maximum number of investigations needed, assuming the suspects are locked within the range $[p_i, q_i]$.

Input Format

The first line contains a single positive integer $n$, the number of suspects.

The next $n$ lines each contain two positive integers $l_i, r_i$, representing the height range of the $i$-th suspect.

The next line contains a single positive integer $q$, the number of queries.

The next $q$ lines each contain two positive integers $p_i, q_i$, representing a query.

Output Format

Output $q$ lines, each containing the answer to the corresponding query.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
1
2

Input Sample #2

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

Output Sample #2

1
1
1

Input Sample #3

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

Output Sample #3

3
1
3

Notes

[Sample 3 Explanation]

• Query $1, 3$: Investigate within the ranges $[1,1], [2,3], [4,5]$, the answer is $3$.
• Query $2$: Investigate within the range $[3,5]$, the answer is $1$.

[Data Range and Constraints]

This problem uses subtask-based testing.

• Subtask 1 (10 pts): $q = p_1 = 1$, $q_1 = n$.
• Subtask 2 (10 pts): $1 \le n, q \le 5000$.
• Subtask 3 (20 pts): $1 \le n \le 5000$.
• Subtask 4 (20 pts): $1 \le q \le 100$.
• Subtask 5 (50 pts): No special restrictions.

For $100\%$ of the data, $1 \le n, q \le 2 \times 10^5$, $1 \le a \le b \le n$, $1 \le l_i \le r_i \le 10^9$, $1 \le p_i \le q_i \le n$.

[Hint and Attribution]

This problem is translated from COCI 2021-2022 CONTEST #2 Task 5 Osumnjičeni.

The score is set according to the original COCI problem, with a maximum score of $110$.

见题面 Input 部分

见题面 Output 部分