#include <bits/stdc++.h>
using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int v[100001];
int caut(int val, int n, int cer)
{
    int pos=0, msk;
    for(msk=1<<20;msk>0;msk/=2)
    if(pos+msk<=n && v[pos+msk]<=val)
        pos+=msk;
    if(cer==2)
    {
        while(v[pos]==val)
            pos--;
        pos++;
        return pos;
    }
    if(cer==1)
    {
        return pos;
    }
    if(cer==0)
    {
        if(v[pos]==val)
            return pos;
        else
            return -1;
    }

}
int main()
{
    int n, m, i, p, x;
    in >> n;
    for(i=1;i<=n;i++)
        in >> v[i];
    in >> m;
    for(i=1;i<=m;i++)
    {
        in >> p >> x;
        out << caut(x,n,p) << '\n';
    }
    return 0;
}