#include <iostream>
#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,v[100001],x,i,t,st,dr,m,k,poz;

int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>v[i];
    f>>k;
    for(i=1;i<=k;i++)
    {
        f>>t>>x;
        if(t==0)
        {
            st=1, dr=n; poz=-1;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(v[m]==x && v[m+1]>x) poz=m, st=dr+1;
                else if(v[m]<=x) st=m+1;
                else if(v[m]>x) dr=m-1;
            }
            g<<poz<<'\n';
        }
        else if(t==1)
        {
            st=1,dr=n,poz=-1;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(v[m]<=x && v[m+1]>x) poz=m, st=dr+1;
                else if(v[m]<=x && v[m+1]<=x) st=m+1;
                else if(v[m]>x) dr=m-1;
            }
            g<<poz<<'\n';
        }
        else
        {
            st=1,dr=n,poz=-1;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(v[m]>=x && v[m-1]<x) poz=m, st=dr+1;
                else if(v[m]>=x && v[m-1]>=x) dr=m-1;
                else if(v[m]<x) st=m+1;
            }
            g<<poz<<'\n';
        }
    }
    return 0;
}