Cho một dãy ~A~, đếm số lượng số trong dãy mang giá trị trong khoảng ~[l, r]~.

Input

• Dòng đầu tiên là số nguyên ~n~ cho biết số phần tử của dãy ~A~.
• Dòng thứ hai gồm ~n~ số nguyên dương, số thứ ~i~ ghi giá trị của phần tử ~A_i~ (~1 \leq n \leq 2 \cdot 10^5~, ~1 \leq A_i \leq 10^9~).
• Dòng thứ ba là số nguyên ~q~ là số lượng truy vấn (~1 \leq q \leq 2 \cdot 10^5~).
• ~q~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên dương ~l_i~, ~r_i~ (~1 \leq l_i \leq r_i \leq 10^9~).

Output

Ghi ra ~q~ dòng, dòng thứ ~i~ tương ứng với câu trả lời cho truy vấn thứ ~i~.

Sample input

5
1 4 9 16 25
3
1 2
1 30
10 15

Sample output

1
5
0

Subtask

• ~30\%~ số test có ~1 \leq n, q \leq 10^3~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.