#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;
            if(v[n]<x) poz=-1;
            else if(v[n]==x) poz=n;
            else
            {
                while(st<=dr)
                {
                    m=st+(dr-st)/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)
        {
            if(v[n]<=x) poz=n;
            else
            {
                st=1,dr=n,poz=-1;
                while(st<=dr)
                {
                    m=st+(dr-st)/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
        {
            if(v[1]>=x) poz=1;
            else
            {
                st=1,dr=n,poz=-1;
                while(st<=dr)
                {
                    m=st+(dr-st)/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;
}