#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
long n,em,v[100001],i,j,a,m;
bool ok=0;
short x;
long caut_binar(long st,long dr,long p)
{ok=0;
 while(st<dr)
   {m=(st+dr)/2;
    if(v[m]==p)
      {if(x==0||x==1)
         while(v[m]==v[m+1])
            m++;
       else
         if(x==2)
           while(v[m]==v[m-1])
             m--;
        return m;
      }
    if(v[m]>p)
        dr=m-1;
    else
        st=m+1;
   }
  m=((st+dr)/2);
  if(x==0)
    return -1;
  if(x==1)
    {if(v[m]<p)
        while(v[m+1]<p)
              m++;
         else
            while(v[m]>p)
              m--;
        }
  if(x==2)
         {if(v[m]<p)
          {while(v[m]<=p)
             m++;
          }
         else
           while(v[m-1]==v[m])
              m--;
         }
 return m;
}
int main()
{f>>n;
 for(i=1;i<=n;i++)
    f>>v[i];
 f>>em;
 for(i=1;i<=em;i++)
  {
    f>>x>>a;
    g<<caut_binar(1,n,a)<<'\n';
  }
f.close();g.close();
return 0;
}