//My first binary_lifting
//https://c...content-available-to-author-only...s.com/edu/course/2/lesson/6/1/practice/contest/283911/problem/D
//Binary lifting is faster then upper_bound and lower_bonud when the dataset is huge.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
int tc,n,i,low,high,m,lift;cin>>n;
vector<int>v(n);
for(auto &it:v){cin>>it;}
sort(v.begin(),v.end());
cin>>tc;
while(tc--)
{
int x=0,y=0,pos_low=0,pos_hi=0;
cin>>low>>high;lift=0;
//Binary lifting of lower_bound
for(i=25;i>=0;i--)
{
lift=(1<<i);
if(lift+pos_low<n)
{
if(v[lift+pos_low]<low){pos_low+=lift;}
}
}if(v[pos_low]<low){pos_low++;}
//Binary lifting of upper_bound
for(i=25;i>=0;i--)
{
lift=(1<<i);
if(lift+pos_hi<n)
{
if(v[lift+pos_hi]<=high){pos_hi+=lift;}
}
}if(v[pos_hi]<=high){pos_hi++;}
cout<<pos_hi-pos_low<<endl;
}
}
Ly9NeSBmaXJzdCBiaW5hcnlfbGlmdGluZwovL2h0dHBzOi8vYy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5jb20vZWR1L2NvdXJzZS8yL2xlc3Nvbi82LzEvcHJhY3RpY2UvY29udGVzdC8yODM5MTEvcHJvYmxlbS9ECi8vQmluYXJ5IGxpZnRpbmcgaXMgZmFzdGVyIHRoZW4gdXBwZXJfYm91bmQgYW5kIGxvd2VyX2JvbnVkIHdoZW4gdGhlIGRhdGFzZXQgaXMgaHVnZS4KI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCmludDMyX3QgbWFpbigpCnsKCWludCB0YyxuLGksbG93LGhpZ2gsbSxsaWZ0O2Npbj4+bjsKCXZlY3RvcjxpbnQ+dihuKTsKCWZvcihhdXRvICZpdDp2KXtjaW4+Pml0O30KCXNvcnQodi5iZWdpbigpLHYuZW5kKCkpOwoJY2luPj50YzsKCXdoaWxlKHRjLS0pCiAgICB7CiAgICAgICAgaW50IHg9MCx5PTAscG9zX2xvdz0wLHBvc19oaT0wOwogICAgICAgIGNpbj4+bG93Pj5oaWdoO2xpZnQ9MDsKCgogICAgICAgIC8vQmluYXJ5IGxpZnRpbmcgb2YgbG93ZXJfYm91bmQKICAgICAgICBmb3IoaT0yNTtpPj0wO2ktLSkKICAgICAgICB7CiAgICAgICAgICAgIGxpZnQ9KDE8PGkpOwogICAgICAgICAgICBpZihsaWZ0K3Bvc19sb3c8bikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYodltsaWZ0K3Bvc19sb3ddPGxvdyl7cG9zX2xvdys9bGlmdDt9CiAgICAgICAgICAgIH0KICAgICAgICB9aWYodltwb3NfbG93XTxsb3cpe3Bvc19sb3crKzt9CgoKICAgICAgICAvL0JpbmFyeSBsaWZ0aW5nIG9mIHVwcGVyX2JvdW5kCiAgICAgICAgZm9yKGk9MjU7aT49MDtpLS0pCiAgICAgICAgewogICAgICAgICAgICBsaWZ0PSgxPDxpKTsKICAgICAgICAgICAgaWYobGlmdCtwb3NfaGk8bikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYodltsaWZ0K3Bvc19oaV08PWhpZ2gpe3Bvc19oaSs9bGlmdDt9CiAgICAgICAgICAgIH0KICAgICAgICB9aWYodltwb3NfaGldPD1oaWdoKXtwb3NfaGkrKzt9CgoKICAgICAgICBjb3V0PDxwb3NfaGktcG9zX2xvdzw8ZW5kbDsKICAgIH0KfQo=