#include<fstream>

using namespace std;

int v[100001];

int c0(int x,int i,int j)
{if(i>j)  return -1;
 int mijl;
 while(i<=j)
  {mijl=(i+j)/2;
   if(x==v[mijl])
     {while(x==v[mijl])   mijl++;
      return (mijl-1);
      }
    else
     if(x<v[mijl])  j=mijl-1;
       else         i=mijl+1;  
    }     
}
 
int c1(int x,int i,int j)
{if(i>j)  return (i-1);
 int mijl;
 while(i<=j)
   {mijl=(i+j)/2;
    if(x==v[mijl])  
      {while(x==v[mijl])  mijl++;
       return (mijl-1);
       }
      else
       if(x<v[mijl])  j=mijl-1;
         else         i=mijl+1;
    }      
} 
  
int c2(int x,int i,int j)
{if(i>j)  return i;
 int mijl;
 while(i<=j)
   {mijl=(i+j)/2;
    if(x==v[mijl])  
      {while(x==v[mijl])  mijl--;
       return (mijl+1);
       }
     else
      if(x<mijl)  j=mijl-1; 
        else      i=mijl+1;
     }   
}  
                 
int main()
{int n,m,i,x,tip;
 ifstream f("cautbin.in");
 ofstream g("cautbin.out");
 f>>n;
 for(i=1;i<=n;i++)
   f>>v[i];
 f>>m;  
 for(i=1;i<=m;i++)
   {f>>tip;
    f>>x;
    if(tip==0)  g<<c0(x,1,n)<<endl;
    else 
      if(tip==1)  g<<c1(x,1,n)<<endl;
        else      g<<c2(x,1,n)<<endl;
    }   
 f.close();
 g.close();
 return 0; 
}