问题描述

具体描述见教材p222： 我有很多(n条)珍珠项链，每天都要从中挑一条戴上......挑哪条很有讲究，不能太难看也不能太好看。所以我希望你能帮帮我，解决这个问题 ——每天帮我算算，那天我能戴的项链有多少条。

格式

输入

第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大小关系不确定）

输出

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

样例

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

限制

1s, 64MB.