#include<fstream>

using namespace std;

int v[100001];

int c0(int x,int i,int j)
{if(i>j)  return -1;
 int mijl=(i+j)/2;
 if(x==v[mijl])
   {while(x==v[mijl])   mijl++;
    return (mijl-1);
    }
  else
   if(x<v[mijl])  return c0(x,i,mijl-1);
     else         return c0(x,mijl+1,j);   
}
 
int c1(int x,int i,int j)
{if(i>j)  return (i-1);
 int mijl=(i+j)/2;
 if(x==v[mijl])  
  {while(x==v[mijl])  mijl++;
   return (mijl-1);
   }
  else
   if(x<v[mijl])  return c1(x,i,mijl-1);
     else         return c1(x,mijl+1,j);  
} 
  
int c2(int x,int i,int j)
{if(i>j)  return i;
 int mijl=(i+j)/2;
 if(x==v[mijl])  
   {while(x==v[mijl])  mijl--;
    return (mijl+1);
    }
   else
    if(x<mijl)  return c2(x,i,mijl-1); 
      else      return c2(x,mijl+1,j);
}  
                 
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; 
}