#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main()
{
    int v[100001],n;
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>v[i];
    long long st=1,dr=n+1,x,c,m,val,val1;
    fin>>x;
    for(int i=1; i<=x; i++)
    {
        fin>>c>>val;
        st=1;
        dr=n+1;
        if(c==0)
        {
            int ok=0;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(v[m]<=val)
                {
                    st=m+1;
                }else if(v[m]>val)
                {
                    dr=m-1;
                }
                if(v[m]==val)
                {
                   val1=m;
                   ok=1;
                }
            }
            if(ok==1)
                fout<<val1<<"\n";
            else
                fout<<"-1"<<"\n";
        }else if(c==1)
        {
            while(st<=dr && st<=n)
            {
                m=(st+dr)/2;
                if(v[m]<=val)
                {
                    st=m+1;
                }else if(v[m]>val)
                {
                    dr=m-1;
                }
            }
            fout<<st-1<<"\n";
        }else if(c==2)
        {
          while(st<=dr)
            {
                m=(st+dr)/2;
                if(v[m]<val)
                {
                    st=m+1;
                }else if(v[m]>=val)
                {
                    dr=m-1;
                }
            }
            fout<<dr+1<<"\n";
        }
    }
    return 0;
}