Background

Special for beginners, ^_^

Description

我有很多珍珠项链，每天要从中挑一条戴上……挑哪条很有讲究，不能太难看也不能太好看。所以我希望你能帮帮我，解决这个问题——每天帮我算算，那天我能戴的项链有多少条。

Format

Input

第1行为正整数n，表示项链的总条数（n《100000）；

第2行有n个整数（代表每条项链的好看程度Xi，0<=Xi<=maxlongint）;

第3行为正整数m，表示总天数（也就是总询问次数，其中m《100000）；

以下m行，每行两个整数Ai，Bi（1<=Ai，Bi<=maxlongint）,询问好看程度在Ai到Bi之间的项链条数（含等于Ai或Bi的，Ai与Bi大小关系不确定）。

Output

输出m行，对于每次询问输出一行，从Ai到Bi(含Ai和Bi)好看程度在Ai到Bi之间的项链条数。

Samples

7
8 2 3 5 6 7 7
6
1 5
8 6
1 10
5 5
4 4
7 8

3
4
7
1
0
3

Limitation

1s, 1024KiB for each test case.