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

                if(b<=x[dr])
                {
                    if(poz==0)   poz=dr;
                    else     if(dr<poz) poz=dr;
                }

                 if(b<=x[mij])
                 {
                     if(poz==0)   poz=mij;
                     else    if(mij<poz) poz=mij;
                 }

                if(b<=x[mij])   dr=mij;
                else if(b>x[mij])  st=mij+1;
            }
            fout << poz;
       }
   }
    return 0;
}