Xác nhận nghi phạm

Tối qua tại thị trấn Mana xảy ra một vụ án nghiêm trọng. Cảnh sát lập tức tiến hành một cuộc điều tra và hiện xác định và tạm giam được \(N\) nghi phạm được đánh số từ 1 đến \(N\). Vừa thời gian diễn ra vào buổi tối nên lúc đấy chỉ có một nhân chứng đi qua và anh ta cũng không thể nhìn được mặt của thủ phạm. Nhân chứng chỉ nhìn được vóng dáng và biết được chiều cao của thủ phạm. Bây giờ nhân chứng sẽ tiến hành xác nhận xem ai là thủ phạm thật sự. Vì tình hình rất hỗn loạn nên phía cảnh sát chỉ có thể ước lượng rằng nghi phạm thứ \(i\) có chiều cao trong khoảng từ \(l_i\) đến \(r_i\). Để giúp nhân chứng nhận diện dễ dàng, cảnh sát sẽ phân các nghi phạm vào trong các phòng. Mỗi phòng sẽ gồm những nghi phạm được đánh số liên tiếp và không có 2 nghi phạm nào có cùng chiều cao (nghĩa là không tồn tại 2 nghi phạm \(i,j\) ở cùng chung phòng mà \([l_i,r_i ] \cap [l_j,r_j] \neq \emptyset\)).

Vì số lượng phòng không có quá nhiều nên đội trưởng đội điều tra hiện đang quan tâm đến câu hỏi rằng: Nếu tội phạm thật sự có chỉ số nằm trong khoảng từ \(a\) đến \(b\) thì số phòng tối thiểu cần sử dụng để điều tra là bao nhiêu.

Yêu cầu: Bạn hãy giúp đội trưởng đội điều tra trả lời \(Q\) câu hỏi như vậy.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N\leq 200000)\) là số nghi phạm.

• Mỗi dòng trong số \(N\) dòng tiếp theo chứa 2 số nguyên dương \(l_i,r_i (l_i\leq r_i\leq 10^9)\) là phạm vi chiều cao của nghi phạm thứ \(i\).

• Dòng tiếp theo chứa số nguyên dương \(Q\) \((Q\leq 200000)\) là số câu hỏi.

• Mỗi dòng trong số \(Q\) dòng tiếp theo gồm 2 số nguyên dương \(a,b (a\leq b \leq N)\).

Output

• Đối với mỗi câu hỏi, hãy in ra số phòng tối thiểu phải sử dụng.

Example

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

Scoring

• Subtask \(1\) \((15\%)\): \(Q=1,a=1,b=N\).

• Subtask \(2\) \((25\%)\): \(N,Q \leq 5000\).

• Subtask \(3\) \((20\%)\): \(N\leq 5000,Q\leq 200000\).

• Subtask \(4\) \((20\%)\): \(N \leq 200000,Q\leq 100\).

• Subtask \(5\) \((20\%)\): Không có giới hạn gì thêm.