#include    <iostream>
#include    <fstream>

using namespace std;

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

int v[100005],n,m;

int cautbin0(int a)
{
    int st=1,dr=100005,p;
    while(st<=dr)
    {
        int mid=st+(dr-st)/2;
        if(v[mid]==a)
            p=mid,st=mid+1;
        else if(v[mid]<a)
            dr=mid-1;
        else st=mid+1;
    }
    if(v[p]==a)
      return p;
    return -1;
}

int cautbin1(int a)
{
    int st=1,dr=100005,p;
    while(st<=dr)
    {
        int mid=st+(dr-st)/2;
        if(v[mid]==a)
            p=mid,st=mid+1;
        else if(v[mid]>a)
            st=mid+1,p=mid;
        else dr=mid-1;
    }
    return p-1;
}

int cautbin2(int a)
{
    int st=1,dr=100005,p;
    while(st<=dr)
    {
        int mid=st+(dr-st)/2;
        if(v[mid]==a)
            p=mid,dr=mid-1;
        else if(v[mid]<a)
            dr=mid-1,p=mid;
        else dr=mid-1;
    }
    return p+1;
}

int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(int j=1;j<=m;j++)
    {
        int v,a;
        in>>v>>a;
        if(!v)
            out<<cautbin0(a)<<'\n';
        else if(v==1)
            out<<cautbin1(a)<<'\n';
        else out<<cautbin2(a)<<'\n';
    }
}