#include <bits/stdc++.h>

using namespace std;
int a[100005],n,m;

int caut0(int x)
{
    int st=1,dr=n,mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid]<=x && a[mid+1]>x) break;
        else if(a[mid]<=x) st=mid+1;
        else dr=mid-1;
    }
    if(a[mid]==x) return mid;
    return -1;
}

int caut1(int x)
{
    int st=1,dr=n,mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid+1]>x && a[mid]<=x) break;
        else if(a[mid]<=x) st=mid+1;
        else dr=mid-1;
    }
    return mid;
}

int caut2(int x)
{
    int st=1,dr=n,mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid]>=x && a[mid-1]<x) break;
        else if(a[mid]<x) st=mid+1;
        else dr=mid-1;
    }
    return mid;
}

int main()
{
    int ok,x,i;
    ifstream fin("cautbin.in");
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    ofstream fout("cautbin.out");
    for(i=1;i<=m;i++)
    {
        fin>>ok>>x;
        if(ok==0) fout<<caut0(x)<<"\n";
        if(ok==1) fout<<caut1(x)<<"\n";
        if(ok==2) fout<<caut2(x)<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}