#include <iostream>
#include <fstream>
using namespace std;
int v[100001];
int n,m;
int binar0(int x)
{
    if (n==1)
    {
        if (v[1]==x)
            return 1;
    }
    int t=1,p=n;
    int aux;   /// t=start, p=stop
    while (p-t>1)
    {
        aux=(t+p)/2;
        if (v[aux]<=x)
        {
            t=aux;
        }
        else
        {
            p=aux-1;
        }
        //cout<<"t="<<t<<"\n";
//cout<<"p="<<p<<"\n";
    }
    if (t==x)
        return t;
        return -1;
}
int binar2(int x)
{
    if (n==1)
    {
        if (v[1]==x)
            return 1;
    }
    int t=1,p=n;
    int aux;   /// t=start, p=stop
    while (p-t>1)
    {
        aux=(t+p)/2;
        if (v[aux]>=x)
        {

            p=aux-1;
        }
        else
        {
            t=aux;
        }
        //cout<<"t="<<t<<"\n";
//cout<<"p="<<p<<"\n";
    }
        return p;
}
int binar1(int x)
{
    if (n==1)
    {
        if (v[1]==x)
            return 1;
    }
    int t=1,p=n;
    int aux;   /// t=start, p=stop
    while (p-t>1)
    {
        aux=(t+p)/2;
        if (v[aux]<=x)
        {
            t=aux;
        }
        else
        {
            p=aux-1;
        }
        //cout<<"t="<<t<<"\n";
//cout<<"p="<<p<<"\n";
    }
        return t;

}
int main()
{
    ifstream in ("cautbin.in");
    ofstream out("cautbin.out");
    in>>n;
    int i;
    for (i=1;i<=n;i++)
    {
        in>>v[i];
    }
    in>>m;
    int c,x;
    for (i=1;i<=m;i++)
        {
          in>>c>>x;
          if (c==0)
          {
              out<<binar0(x)<<"\n";

          }
          if (c==1)
          {
      out<<   binar1(x)<<"\n";


          }
          if (c==2)
          {
out<<            binar2(x);
          }
        }
}