Time Limit: 3 Sec  Memory Limit: 128 MB

Description

Alice likes playing games. So she will take part in the movements of M within N days, and each game is represented in an integer between 1 and M. Roommates have Q magic questions: How many different kinds of games does Alice participate between Lth day and Rth day(including Lth day and Rth day)?

Input

You will be given a number of cases; each case contains blocks of several lines. The first line contains 2 numbers of N and M. The second line contains N numbers implying the game numbers that Alice take part in within N days. The third line contains a number of Q. Then Q lines is entered. Each line contain two numbers of L and R.

1≤N,M,Q≤100000

Output

There should be Q output lines per test case containing Q answers required.

Sample Input

5 3 1 2 3 2 2 3 1 4 2 4 1 5

Sample Output

3 2 3

HINT

---

 

这是今年校赛的K题，一道经典题目，但现场没A。

在线可以用主席树，目前还不会。有一个巧妙的利用数状数组的离线解法，比较好写。

要点是：

1.将查询按右端点从小到大排序。

2.将每个数上一次出现的位置记录下来。当这个数再次出现时，将它上次出现位置上的计数消除。

Implementation:

主体是个双指针。

#include 
     
      using namespace std;const int N(1e5+5);int n, m, q, a[N], pos[N], bit[N], ans[N];void add(int x, int v){    for(; x<=n; bit[x]+=v, x+=x&-x);}int sum(int x){    int res=0;    for(; x; res+=bit[x], x-=x&-x);    return res;}struct P{    int l, r, id;    P(int l, int r, int id):l(l),r(r),id(id){}    P(){};    bool operator<(const P&b)const{
   return r