Given an array a of n integers a1, a2,..., an. Learn how to answer questions quickly "How many numbers have values from l to r"?
Input
The first line contains an integer n (1<=n<=105) — the length of the array. The second line contains n integers a1, a2,..., an (−109<=ai<=109). The third line contains an integer k (1<=k<=105) — number of requests. The following k lines contain pairs of numbers l r (−109<=l<=r<=10 9).
Output
Print k numbers (each on a separate line) responses.
Examples
| # |
Input |
Output |
| 1 |
5
10 1 10 3 4
4
1 10
29
3 4
2 2
|
5
2
2
0
|