#include <iostream>
#include <fstream>
#include <cmath>
#include <climits>
using namespace std;

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

int n,m,a[100001],q,t,r0;
int main()
{

    fin>>n;
   for(int i=1;i<=n;i++)
   {
       fin>>a[i];
   }
   fin>>m;
    for(int i=1;i<=m;i++)
   {
       fin>>q>>t;
   if(q==0)
   {
        int st=1, dr=n;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(a[mij]==t && a[mij+1]>t)
            {
                fout<<mij<<"\n";
                break;
            }
            if(a[mij]<=t)
            {
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
        if(st>dr)
        {
            fout<<-1;
        }
   }
   if(q==1)
   {
    int st=1,dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(a[mij+1]>t && a[mij]<=t)
        {
            fout<<mij<<"\n";
            break;
        }
       if(t<a[mij])
       {
           dr=mij-1;
       }
       else
            st=mij+1;
    }
   }
   if(q==2)
   {
    int st=1,dr=n;
    while(st<=dr)
    {
    int mij=(st+dr)/2;
        if(a[mij]>=t && a[mij-1]<t)
        {
            fout<<mij<<"\n";
            break;
        }
       if(t<a[mij])
       {
           st=mij-1;
       }
       else
            dr=mij+1;
    }
   }
   }
    return 0;
}