#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int i,j,a[100001],n,m,x,tip;
int cautbin0(int i,int j,int x)
{
    while (i<=j)
    {
         int mij=(i+j)/2;

         if(a[mij]<=x) i=mij+1;
            else j=mij-1;
    }
    int mij=(i+j)/2;

    if(a[mij]>x) mij--;
    if(a[mij]==x) return mij;
          else    return -1;


}

int cautbin1(int i,int j,int x)
{
    while (i<j)
    {
         int mij=(i+j)/2;

         if(a[mij]<=x) i=mij+1;
            else j=mij;
    }
    int mij=(i+j)/2;

    if(a[mij]>x) mij--;
    return mij;


}
int cautbin2(int i,int j,int x)
{
    while (i<j)
    {
         int mij=(i+j)/2;

         if(a[mij]<x) i=mij+1;
            else j=mij;
    }
    int mij=(i+j)/2;

    if(a[mij]<x) mij++;

    return mij;

}
int main ()
{
    f>>n;
    for(i=1;i<=n;i++)
    f>>a[i];

    f>>m;
    for(j=1;j<=m;j++)
    {
        f>>tip>>x;
        if(tip==0) g<<cautbin0(1,n,x)<<endl;
         else if(tip==1) g<<cautbin1(1,n,x)<<endl;
           else if(tip==2) g<<cautbin2(1,n,x)<<endl;
    }

  return 0;
}