#include <iostream>
#include <fstream>

using namespace std;

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

int bin0(int v[],int n,int x)
{
    int st=1,dr=n;
    while(st<dr)
    {
        int m=st+(dr-st)/2;
        if(v[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }
    int m=st+(dr-st)/2;
    if(v[m]>x)m--;
    if(v[m]==x)return m;
    return -1;
}

int bin1(int v[],int n,int x)
{
    int m,st=1,dr=n;
    while(st<dr)
    {
        m=st+(dr-st)/2;
        if(v[m]==x)
            return m;
        else if(v[m]<x)
            st=m+1;
        else
            dr=m+1;
    }
    m=st+(dr-st)/2;
    if(v[m]>x)m--;
    if(v[m]<=x)
        return m;
    return -1;
}

int bin2(int v[],int n,int x)
{
    int st=1,dr=n,m;
    while(st<dr)
    {
        m=st+(dr-st)/2;
        if(v[m]==x)
            return m;
        else if(v[m]<x)
            st=m+1;
        else
            dr=m-1;
    }
    m=st+(dr-st)/2;
    if(v[m]<x)
        m++;
    if(v[m]>x)
        return m;
    return -1;
}

int main()
{
    int n,m,i,k,x,v[100002];
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>k>>x;
        if(k==0)
            fout<<bin0(v,n,x)<<"\n";
        else if(k==1)
            fout<<bin1(v,n,x)<<"\n";
        else if(k==2)
            fout<<bin2(v,n,x)<<"\n";
    }
    return 0;
}