Mô tả bài toán

Một trò chơi yêu cầu tìm số lượng khán giả phù hợp nhất với từng người chơi dựa trên điểm số của khán giả và khoảng điểm phù hợp của người chơi.

Input:

• Dòng đầu tiên chứa một số nguyên ~ n ~ (~ 0 \leq n \leq 10^5 ~), là số lượng khán giả.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ a_1, a_2, \ldots, a_n ~ (~ 1 \leq a_i \leq 10^9 ~), là điểm số của mỗi khán giả.
• Dòng thứ ba chứa một số nguyên ~ m ~ (~ 1 \leq m \leq 10^5 ~), là số lượng người chơi.
• ~ m ~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~ s_i ~ và ~ f_i ~ (~ 1 \leq s_i \leq f_i \leq 10^9 ~), là khoảng điểm phù hợp của người chơi thứ ~ i ~.

Output:

• ~ m ~ dòng, mỗi dòng chứa số lượng khán giả phù hợp với người chơi thứ ~ i ~.

Ví dụ:

Input:

5
7 2 4 5 3
2
1 4
3 10

Output:

3
4