#include <iostream>
#include <fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

int v[100001],n,m;

int cer0(int k)
{
      if(v[n]==k)
        return n;
    int aux,left=1,right=n;
    while(left+1<right)
    {
        aux=(left+right)/2;
        if(v[aux]<=k)
            left=aux;
        else
            right=aux;

    }
    if(k!=v[left])
        return -1;
    return left;
}

int cer1(int k)
{
    int ye=cer0(k);
    if(ye!=-1)
        return ye;

    if(v[n]<=k)
        return n;

    int aux,left=1,right=n;
    while(left+1<right)
    {
        aux=(left+right)/2;
        if(v[aux]<=k)
            left=aux;
        else
            right=aux;

    }
    return left;


}

int cer2(int k)
{

    if(v[1]>=k)
        return 1;

    int aux,left=1,right=n;
    while(left<right)
    {
        aux=(left+right)/2;
        if(v[aux]<k)
            left=aux+1;
        else
            right=aux;

    }
    return left;


}

int main()
{
    in>>n;
    int cer,nr;

    for(int i=1;i<=n;i++)
      in>>v[i];

    in>>m;

    for(int i=1;i<=m;i++)
    {
        in>>cer;
        in>>nr;

        if(cer==0)
            out<<cer0(nr)<<'\n';
        else if (cer==1)
            out<<cer1(nr)<<'\n';
        else
            out<<cer2(nr)<<'\n';
    }


    return 0;
}