#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[1000005],N,M,x,y;
void cauta(int x, int y, int st, int dr)
{
   int mijl;
   bool gasit=false;
   while(!gasit && st<=dr)
   {
       mijl=st+(dr-st)/2;
       if(v[mijl]==y)
       {
           gasit=true;
           if(x<=1)
             {while(v[mijl]==y && mijl<=N)
                 mijl++;
              g<<mijl-1<<'\n';}
           else
              {while(v[mijl]==y && mijl>=1)
                 mijl--;
              g<<mijl+1<<'\n';}
       }
       else if(v[mijl]<y) st=mijl+1;
       else dr=mijl-1;
   }

   if(!gasit)
     {  if(x==0) g<<"-1"<<'\n';
        if(x==1) g<< dr <<'\n';
        if(x==2) g<< st <<'\n'; }
}
int main()
{
    f>>N;
    for(int i=1; i<=N; i++)
        f>>v[i];

    f>>M;
    for(int i=1;i<=M;i++)
    {
       f>>x>>y;
       cauta(x,y,1,N);

    }
    f.close();
    g.close();
    return 0;
}