#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long long a[110000],rsp[110000],intb,nr;
int m,n,l,r,mij;
int main()
{

    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for(int i=1;i<=m;i++)
        {
            fin>>intb>>nr;
            if(intb==0)
            {
                l=1;
                r=n;
                mij=l+(r-l)/2;
                while(l<=r)
                {
                    if(mij<=nr)
                        l=mij+1;
                    else if(mij>nr)
                        r=mij-1;
                    mij=l+(r-l)/2;
                }
                if(a[l]!=nr)
                    rsp[i]=r;
                else if(a[r]!=nr)
                    rsp[i]=l;
                else if(a[r]==nr && a[l]==nr)
                    rsp[i]=max(l,r);
                else rsp[i]=-1;

            }
            else if(intb==1)
            {
                l=1;
                r=n;
                mij=l+(r-l)/2;
                while(l<=r)
                {
                    if(mij<=nr)
                        l=mij+1;
                    else if(mij>nr)
                        r=mij-1;
                    mij=l+(r-l)/2;
                }
                if(a[l]<=nr)
                    rsp[i]=l;

            }
            else if(intb==2)
            {
                l=1;
                r=n;
                mij=l+(r-l)/2;
                while(l!=r)
                {
                    if(mij<nr)
                        l=mij+1;
                    else if(mij>=nr)
                        r=mij-1;
                    mij=l+(r-l)/2;
                }
                if(a[r]>=nr)
                    rsp[i]=r;
            }

        }
    for(int i=1;i<=m;i++)
        fout<<rsp[i]<<"\n";
    return 0;
}