#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100005],n,st,dr,y,mid,M,x;

int caut0(int x)
{ int poz=-1;
    for(st=1,dr=n;st<=dr;)
    { mid=(st+dr)/2;
    if(v[mid]>x) dr=mid-1;
    else if(v[mid]<x) st=mid+1;
    else { poz=mid; st=mid+1; }
    }
return poz;
}

int caut1(int x)
{ int poz=0;
    for(st=1,dr=n;st<=dr;)
    { mid=(st+dr)/2;
    if(v[mid]>x) dr=mid-1;
    else if(v[mid]<=x) { poz=mid; st=mid+1; }
    }
return poz;
}

int caut2(int x)
{ int poz=0;
    for(st=1,dr=n;st<=dr;)
    { mid=(st+dr)/2;
    if(v[mid]>=x) { poz=mid; dr=mid-1; }
    else if(v[mid]<x) st=mid+1;
    }
return poz;
}
int main()
{
  f>>n;
  for(int i=1;i<=n;i++)
     f>>v[i];
  f>>M;
  for(int i=1;i<=M;i++)
  {
      f>>y>>x;
      if(y==0)g<<caut0(x)<<"\n";
       else if(y==1)g<<caut1(x)<<"\n";
        else g<<caut2(x)<<"\n";
  }
}