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

        else if(c==1)
        {
         st=1,dr=n,poz=0;
         while(st<=dr){
           m=(st+dr)/2;
           if(a[m]<=x) poz=m,st=m+1;
           else dr=m-1;
         }
         fout<<poz<<'\n';
        }


        else if(c==2)
        {
            st=1;
            dr=n;
            poz=0;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(a[m]>=x) poz=m,dr=m-1;
                else st=m+1;
            }
            fout<<poz<<'\n';
        }
    }
    return 0;
}