#include <fstream>
using namespace std;
int v[100100];
int caut1 (int st, int dr, int y)
{
    int ans=-1;
    while(st<=dr)
    {
      int mij=(st+dr)/2;
      if(v[mij]<=y)
      {
         ans=mij;
         st=mij+1;
      }
      else
      {
         dr=mij-1;
      }
     }
     return ans;
}
int caut2 (int st, int dr, int y)
{
    int ans=-1;
    while(st<=dr)
    {
      int mij=(st+dr)/2;
      if(v[mij]>=y)
      {
         ans=mij;
         dr=mij-1;
      }
      else
      {
         st=mij+1;
      }
    }
    return ans;
}
int caut3 (int st, int dr, int y)
{
    int ans=-1;
    while(st<=dr)
    {
      int mij=(st+dr)/2;
      if(v[mij]<=y)
      {
         if(v[mij]==y) ans=mij;
         st=mij+1;
      }
      else
      {
         dr=mij-1;
      }
     }
     return ans;
}
int main() {

    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int n,m,i,x,y;
    in>>n;
    for(i=1;i<=n;i++) in>>v[i];
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y;
        int st=1;
        int dr=n;
        if(x==1) out<<caut1(st,dr,y)<<'\n';
        else if(x==2) out<<caut2(st,dr,y)<<'\n';
        else out<<caut3(st,dr,y)<<'\n';
    }
    return 0;
}