#include<iostream>
#include<fstream>
using namespace std ;
ifstream f("cautbin.in") ;
ofstream g("cautbin.out") ;
int v[100001] ;
int cbin0(int st, int dr, int x, int n)
{
  if(st<=dr)
  {
      int mij=(st+dr)/2 ;
      if(v[mij]>x) return cbin0(st, mij-1,x,n) ;
      if(v[mij]<=x)
      {
          if(v[mij]==x) {if(mij==n) return mij ;
                            else if(v[mij+1]==x) return cbin0(mij+1,dr,x,n) ;
                               else return mij ;

                            }
          else return cbin0(mij,dr,x,n) ;
      }
  }
  else return -1 ;
}
int cbin1(int st, int dr, int x, int n)
{
    if(st<=dr)
    {
        int mij=(st+dr)/2 ;
        if(v[mij]>x) return cbin1(st,mij-1,x,n) ;
        else if(v[mij]<=x)

            if(mij==n) return mij ;
              else if(v[mij+1]<=x) return cbin1(mij+1,dr,x,n) ;
                else return mij ;

    }

}
int cbin2(int st, int dr, int x, int n)
{
    if(st<=dr)
    {
        int mij=(st+dr)/2 ;
        if(v[mij]<x) return cbin2(mij+1,dr,x,n) ;
          else if(v[mij]>=x)
                  if(mij==1) return mij ;
                    else if(v[mij-1]>=x) return cbin2( st,mij-1,x,n) ;
                      else return mij ;
    }
}
int main()
{
    int i,n,p,x,y ;
    f>>n ;
    for(i=1;i<=n;i++) f>>v[i] ;
    f>>p ;
    for(i=1;i<=p;i++)
    {
        f>>x>>y ;
        if(x==0) g<<cbin0(1,n,y,n)<<endl  ;
        if(x==1) g<<cbin1(1,n,y,n)<<endl  ;
        if(x==2) g<<cbin2(1,n,y,n)<<endl  ;
    }

}