#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,v[100001],m,q,x;

int main()
{
    fin >> n;
    int i,st,dr,mij,poz;
    for(i=1;i<=n;i++)
    {
        fin >> v[i];
    }
    fin >> m;
    for(i=1;i<=m;i++)
    {
        fin >> q >> x;
        if(q==0)
        {
            poz=-1;
            st=1;
            dr=n;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij]<=x)
                {
                    st=mij+1;
                    poz=mij;
                }
                else dr=mij-1;
            }
            if(poz!=-1 && v[poz]==x) fout << poz << '\n';
            else fout << -1 << '\n';
        }
        else if(q==1)
        {
            poz=-1;
            st=1;
            dr=n;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij]<=x)
                {
                    st=mij+1;
                    poz=mij;
                }
                else dr=mij-1;
            }
            if(v[poz]<=x and poz!=-1) fout << poz << '\n';
            else fout << -1 << '\n';
        }
        else if(q==2)
        {
            poz=-1;
            st=1;
            dr=n;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij]>=x)
                {
                    dr=mij-1;
                    poz=mij;
                }
                else st=mij+1;
            }
            if(v[poz]>=x and poz!=-1) fout << poz <<'\n';
            else fout << -1 << '\n';
        }
    }
    return 0;
}