#include <fstream>
#define Nmax 100001

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int v[Nmax];
int bsearch0(int p,int u,int x)
{
    int m;
    while(p<=u)
    {
        m=p+(u-p)/2;
        if(v[m]<=x)
            p=m+1;
        else
            u=m-1;
    }
    m=p+(u-p)/2;
    if(v[m]>x)
        --m;
    if(v[m]==x)
        return m;
    return -1;
}
int bsearch1(int p,int u,int x)
{
    int m;
    while(p<u)
    {
        m=p+(u-p)/2;
        if(v[m]<=x)
            p=m+1;
        else
            u=m;
    }
    m=p+(u-p)/2;
    if(v[m]>x)
        --m;
    return m;
}
int bsearch2(int p,int u,int x)
{
    int m;
    while(p<u)
    {
        m=p+(u-p)/2;
        if(v[m]<x)
            p=p+1;
        else
            u=m;
    }
    m=p+(u-p)/2;
    if(v[m]<x)
       ++m;
        return m;
}

int main()
{
    int n,t,tip,val;
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];

    f>>t;
    while(t --)
    {
      f>>tip>>val;
      if(tip==0)
      g<<bsearch0(1, n, val)<<"\n";
      if(tip==1)
      g<<bsearch1(1, n, val)<<"\n";
      if(tip==2)
      g<<bsearch2(1, n, val)<<"\n";
    }
}