描述

格式

输入格式

第一行包含三个整数N,M,K，表示矩形的大小与询问的个数。

第二行包含N个数Ai，第i个数表示横坐标为i的点的纵坐标。

接下来包含K行，每一行包含两个整数Li,Ri，表示询问。

输出格式

输出包含K行，分别是K个询问的答案。

样例

样例输入

7 7 5
4 5 6 6 5 7 4
6 6
5 6
3 5
3 7
1 7

样例输出

0
0
1
1
6

限制

每个测试点1.5s,768MB

提示

数据范围：
1 ≤ Ai ≤ M
1 ≤ Li ≤ Ri ≤ N

对于20%的数据，1 ≤ N, M, K ≤ 1000
对于80%的数据，1 ≤ N, M, K ≤ 100000
请注意本题数据较大时限较小，请使用快速的读入输出方式，尽量的避免常数大的算法。

Source

KEKE_046 && Bill_Yang 搬运自CodeChef QCHEF