#include<stdio.h>
#include<algorithm>
#include<string.h> //for memset
#include<vector>
using namespace std;
#define MAX 30009
struct input
{
int s,e,val,p; //p for position, -1 for update, value for query position
};
int lastpos[1000009]; //To store previous occurance of the integer
int bit[MAX]; //Stores count of distinct integers in a given range
void update(int val,int pos)
{
while(pos<MAX)
{
bit[pos]+=val;
pos=pos+(pos&-pos);
}
}
int query(int pos)
{
int sum=0;
while(pos>0)
{
sum+=bit[pos];
pos=pos-(pos&-pos);
}
return sum;
}
int cmp(struct input f,struct input s)
{
if(f.e<s.e)
return 1;
if(f.e>s.e)
return 0;
if(f.s<=s.s)
return 1;
return 0;
}
int main()
{
int n,ip,q,a,b;
memset(bit,0,sizeof(bit));
memset(lastpos,0,sizeof(lastpos));
vector <struct input> abc;
scanf("%d",&n);
for(int i=0;i<n;i++) //stores the array
{
scanf("%d",&ip);
struct input temp;
temp.s=temp.e=i+1; //start and end point equal, i+1 as 1 based indexing
temp.val=ip; //value at the array position
temp.p=-1; //-1 means update operation
abc.push_back(temp);
}
scanf("%d",&q);
int ans[q]; //stores answer for each query
memset(ans,0,sizeof(ans));
for(int i=0;i<q;i++)
{
struct input temp;
scanf("%d%d",&a,&b); //query range
temp.s=a;
temp.e=b;
temp.val=0; //Value of range is not required, any random value should work
temp.p=i; //query number
abc.push_back(temp);
}
sort(abc.begin(),abc.end(),cmp);
// for(int i=0;i<abc.size();i++)
// {
// printf("start = %d \t end = %d\n",abc[i].s,abc[i].e);
// }
for(int i=0;i<abc.size();i++)
{
if(abc[i].p!=-1) //query
{
int t=query(abc[i].e)-query(abc[i].s-1);
ans[abc[i].p]=t;
}
else
{
if(lastpos[abc[i].val]==0) //means not occured, as we are using 1 based indexing
{
lastpos[abc[i].val]=abc[i].s; //last occuring position is the present position
update(1,lastpos[abc[i].val]); //add 1 to the last occuring position
}
else
{
update(-1,lastpos[abc[i].val]); //remove the previous last occured position
lastpos[abc[i].val]=abc[i].s; //last occuring position is the present position
update(1,lastpos[abc[i].val]); //add 1 to the last occuring position
}
}
}
for(int i=0;i<q;i++)
printf("%d\n",ans[i]);
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8YWxnb3JpdGhtPgojaW5jbHVkZTxzdHJpbmcuaD4JLy9mb3IgbWVtc2V0CiNpbmNsdWRlPHZlY3Rvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBNQVggMzAwMDkKc3RydWN0IGlucHV0CnsKCWludCBzLGUsdmFsLHA7CS8vcCBmb3IgcG9zaXRpb24sIC0xIGZvciB1cGRhdGUsIHZhbHVlIGZvciBxdWVyeSBwb3NpdGlvbgp9OwppbnQgbGFzdHBvc1sxMDAwMDA5XTsJLy9UbyBzdG9yZSBwcmV2aW91cyBvY2N1cmFuY2Ugb2YgdGhlIGludGVnZXIKaW50IGJpdFtNQVhdOwkJLy9TdG9yZXMgY291bnQgb2YgZGlzdGluY3QgaW50ZWdlcnMgaW4gYSBnaXZlbiByYW5nZQoKdm9pZCB1cGRhdGUoaW50IHZhbCxpbnQgcG9zKQp7Cgl3aGlsZShwb3M8TUFYKQoJewoJCWJpdFtwb3NdKz12YWw7CgkJcG9zPXBvcysocG9zJi1wb3MpOwoJfQp9CmludCBxdWVyeShpbnQgcG9zKQp7CglpbnQgc3VtPTA7Cgl3aGlsZShwb3M+MCkKCXsKCQlzdW0rPWJpdFtwb3NdOwoJCXBvcz1wb3MtKHBvcyYtcG9zKTsKCX0KCXJldHVybiBzdW07Cn0KaW50IGNtcChzdHJ1Y3QgaW5wdXQgZixzdHJ1Y3QgaW5wdXQgcykKewoJaWYoZi5lPHMuZSkKCQlyZXR1cm4gMTsKCWlmKGYuZT5zLmUpCgkJcmV0dXJuIDA7CglpZihmLnM8PXMucykKCQlyZXR1cm4gMTsKCXJldHVybiAwOwp9CmludCBtYWluKCkKewoJaW50IG4saXAscSxhLGI7CgltZW1zZXQoYml0LDAsc2l6ZW9mKGJpdCkpOwoJbWVtc2V0KGxhc3Rwb3MsMCxzaXplb2YobGFzdHBvcykpOwoJdmVjdG9yIDxzdHJ1Y3QgaW5wdXQ+IGFiYzsKCXNjYW5mKCIlZCIsJm4pOwoJZm9yKGludCBpPTA7aTxuO2krKykJCS8vc3RvcmVzIHRoZSBhcnJheQkKCXsKCQlzY2FuZigiJWQiLCZpcCk7CgkJc3RydWN0IGlucHV0IHRlbXA7CgkJdGVtcC5zPXRlbXAuZT1pKzE7CS8vc3RhcnQgYW5kIGVuZCBwb2ludCBlcXVhbCwgaSsxIGFzIDEgYmFzZWQgaW5kZXhpbmcKCQl0ZW1wLnZhbD1pcDsJCS8vdmFsdWUgYXQgdGhlIGFycmF5IHBvc2l0aW9uCgkJdGVtcC5wPS0xOwkJLy8tMSBtZWFucyB1cGRhdGUgb3BlcmF0aW9uCgkJYWJjLnB1c2hfYmFjayh0ZW1wKTsKCX0KCXNjYW5mKCIlZCIsJnEpOwoJaW50IGFuc1txXTsJLy9zdG9yZXMgYW5zd2VyIGZvciBlYWNoIHF1ZXJ5CgltZW1zZXQoYW5zLDAsc2l6ZW9mKGFucykpOwoJZm9yKGludCBpPTA7aTxxO2krKykKCXsKCQlzdHJ1Y3QgaW5wdXQgdGVtcDsKCQlzY2FuZigiJWQlZCIsJmEsJmIpOwkvL3F1ZXJ5IHJhbmdlCgkJdGVtcC5zPWE7CgkJdGVtcC5lPWI7CgkJdGVtcC52YWw9MDsJCS8vVmFsdWUgb2YgcmFuZ2UgaXMgbm90IHJlcXVpcmVkLCBhbnkgcmFuZG9tIHZhbHVlIHNob3VsZCB3b3JrCgkJdGVtcC5wPWk7CQkvL3F1ZXJ5IG51bWJlcgoJCWFiYy5wdXNoX2JhY2sodGVtcCk7Cgl9Cglzb3J0KGFiYy5iZWdpbigpLGFiYy5lbmQoKSxjbXApOwoJCi8vCWZvcihpbnQgaT0wO2k8YWJjLnNpemUoKTtpKyspCi8vCXsKLy8JCXByaW50Zigic3RhcnQgPSAlZCBcdCBlbmQgPSAlZFxuIixhYmNbaV0ucyxhYmNbaV0uZSk7Ci8vCX0KCWZvcihpbnQgaT0wO2k8YWJjLnNpemUoKTtpKyspCgl7CgkJaWYoYWJjW2ldLnAhPS0xKQkvL3F1ZXJ5CgkJewoJCQlpbnQgdD1xdWVyeShhYmNbaV0uZSktcXVlcnkoYWJjW2ldLnMtMSk7CgkJCWFuc1thYmNbaV0ucF09dDsKCQl9CgkJZWxzZQoJCXsKCQkJaWYobGFzdHBvc1thYmNbaV0udmFsXT09MCkJLy9tZWFucyBub3Qgb2NjdXJlZCwgYXMgd2UgYXJlIHVzaW5nIDEgYmFzZWQgaW5kZXhpbmcKCQkJewoJCQkJbGFzdHBvc1thYmNbaV0udmFsXT1hYmNbaV0uczsJLy9sYXN0IG9jY3VyaW5nIHBvc2l0aW9uIGlzIHRoZSBwcmVzZW50IHBvc2l0aW9uCgkJCQl1cGRhdGUoMSxsYXN0cG9zW2FiY1tpXS52YWxdKTsJLy9hZGQgMSB0byB0aGUgbGFzdCBvY2N1cmluZyBwb3NpdGlvbgoJCQl9CgkJCWVsc2UKCQkJewoJCQkJdXBkYXRlKC0xLGxhc3Rwb3NbYWJjW2ldLnZhbF0pOwkvL3JlbW92ZSB0aGUgcHJldmlvdXMgbGFzdCBvY2N1cmVkIHBvc2l0aW9uCgkJCQlsYXN0cG9zW2FiY1tpXS52YWxdPWFiY1tpXS5zOwkvL2xhc3Qgb2NjdXJpbmcgcG9zaXRpb24gaXMgdGhlIHByZXNlbnQgcG9zaXRpb24KCQkJCXVwZGF0ZSgxLGxhc3Rwb3NbYWJjW2ldLnZhbF0pOwkvL2FkZCAxIHRvIHRoZSBsYXN0IG9jY3VyaW5nIHBvc2l0aW9uCgkJCX0KCQl9Cgl9Cglmb3IoaW50IGk9MDtpPHE7aSsrKQoJCXByaW50ZigiJWRcbiIsYW5zW2ldKTsKfQ==