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