#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long long v[100001];
int main()
{
    int n,i,s,d,m,x,l,q,mid;
    fin>>n;
    for(i=1;i<=n;i++)
    fin>>v[i];
    fin>>mid;
    for(q=1;q<=mid;q++)
    {
        fin>>l>>x;
        if(l==0){
            s=1;
        d=n;
        while(s<d){
            m=(s+d)/2;
            if(v[m]>x)
                d=m;
            else
                s=m+1;
        }
        d--;
        if(v[d]==x)
            fout<<d<<'\n';
            else
            fout<<-1<<'\n';
        }
        else if(l==1){
           s=1;
        d=n;
        while(s<d){
            m=(s+d)/2;
            if(v[m]>x)
                d=m;
            else
                s=m+1;
        }
        d--;
            fout<<d<<'\n';
        }
        else
        {
              s=1;
        d=n;
        while(s<d){
            m=(s+d)/2;
            if(v[m]>=x)
                d=m;
            else
                s=m+1;
        }
            fout<<d<<'\n';
        }
        }
    }