#include <fstream>

using namespace std;

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

int cautbin0(int a[],int n,int x)
{
    int s=0,d=n-1,m;

    while(s<=d)
    {
        m=(s+d)/2;
        if(a[m]<=x) s=m+1;
            else d=m-1;
    }
    m=(s+d)/2;
    if(a[m]>x) m--;
    if(a[m]==x) return m+1;
        else return -1;
}

int cautbin1(int a[],int n,int x)
{
    int s=0,d=n-1,m;

    while(s<d)
    {
        m=(s+d)/2;
        if(a[m]<=x) s=m+1;
            else d=m;
    }

    m=(s+d)/2;
    if(a[m]>x) m--;
    return m+1;
}

int cautbin2(int a[],int n,int x)
{
    int i,s=0,d=n-1,m;

    while(s<d)
    {
        m=(s+d)/2;
        if(a[m]<x) s=m+1;
            else d=m;
    }

    m=(s+d)/2;
    if(a[m]<x) m++;
    return m+1;
}

int main()
{
    int n,m,i,a[100000],x,intrebare;

    in>>n;
    for(i=0;i<n;i++)
        in>>a[i];

    in>>m;

    for(i=0;i<m;i++)
    {
        in>>intrebare;
        in>>x;
        if(intrebare==0) out<<cautbin0(a,n,x)<<"\n";
        if(intrebare==1) out<<cautbin1(a,n,x)<<"\n";
        if(intrebare==2) out<<cautbin2(a,n,x)<<"\n";
    }
    in.close();
    out.close();
    return 0;
}