#include <fstream>

using namespace std;

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

int m,n,v[100010],z,x,k,i,j;
int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>v[i];
    fin>>k;
    while(k--)
        {fin>>z>>x;
         if(z==0)
            { i=1;j=n;
              while(i<j)
                { m=(i+j)/2;
                  if(x==v[m]){while(x==v[m])++m;
                              --m;
                              break;}
                  if(x<v[m])j=m-1;
                  else i=m+1;
                }
              if(i<j)fout<<m<<'\n';
              else fout<<"-1"<<'\n';
            }

         if(z==1)
            { i=1;j=n;
              while(i<j)
                { m=(i+j)/2;
                  if(x==v[m]){while(x==v[m])++m;
                              --m;
                              break;}
                  if(x<v[m])j=m-1;
                  else i=m+1;
                }

              if(v[m]>x)--m;
              fout<<m<<'\n';

            }

         if(z==2)
            { i=1;j=n;
              while(i<j)
                { m=(i+j)/2;
                  if(x==v[m]){while(x==v[m])--m;
                              ++m;
                              break;}

                }

              if(v[m]<x)++m;
              fout<<m<<'\n';

            }

        }


    fin.close(); fout.close();
    return 0;
}