#include <fstream>

using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
int n,k,i,m,a[1000000],dr,st,poz,mij,x;
int main()
{
    fin>>n;
    for (i=1;i<=n;i++) fin>>a[i];
    fin>>m;
    for (i=1;i<=m;i++)
            {fin>>k>>x;
             if  (k==0)
                    {
                        dr=n;st=1;poz=0;
                        while (st<dr)
                       { mij=(st+dr)/2;
                         if (a[mij]==x) {poz=mij;
                                         st=mij+1;
                                         }
                        if (x<a[mij]) dr=mij-1;
                        else st=mij+1;
                       }
                       if (poz==0) fout<<-1<<endl;
                       else fout<<poz<<endl;

                        }
            if (k==1)
                {
                     dr=n;st=1;poz=0;

                      while (st<dr)
                    { mij=(st+dr)/2;
                      if (a[mij]<=x) if (poz<mij) {st=mij+1;
                                                   poz=mij;}
                      if (a[mij]>x) dr=mij-1;
                    }
                    fout<<poz<<endl;
                }
                if (k==2)
                {
                    dr=n;st=1;poz=n+1;

                      while (st<dr)
                    { mij=(st+dr)/2;
                      if (a[mij]>=x) if (poz>mij) {dr=mij-1;
                                                   poz=mij;}
                      if (a[mij]<x) st=mij+1;
                    }
                    fout<<poz<<endl;

                }




            }

}