#include <bits/stdc++.h>

using namespace std;

int n,m,c,x,a[100005];

int Caut0(int x, int l, int r)
{
    if(l==r && a[l]!=x) return -1;
    int mid=(l+r)/2;
    if(mid>x) Caut0(x,l,mid);
    else if(mid<x) Caut0(x,mid,r);
    else{
        while(a[mid]==x) mid++;
        return --mid;
    }
}
int Caut1(int x, int l, int r)
{
    if(l==r){
        while(a[l]<=x) l++;
        return --l;
    }
    int mid=(l+r)/2;
    if(mid>x) Caut1(x,l,mid);
    else if(mid<x) Caut1(x,mid,r);
    else{
        while(a[mid]==x) mid++;
        return --mid;
    }
}
int Caut2(int x, int l, int r)
{
    if(l==r){
        while(a[l]>=x) l--;
        return ++l;
    }
    int mid=(l+r)/2;
    if(mid>x) Caut2(x,l,mid);
    else if(mid<x) Caut2(x,mid,r);
    else{
        while(a[mid]==x) mid--;
        return ++mid;
    }
}

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    in >> n;
    for(int i=1;i<=n;i++) in >> a[i];
    in >> m;
    for(int i=1;i<=m;i++){
        in >> c >> x;
        if(c==0) out << Caut0(x,1,n) << '\n';
        else if(c==1) out << Caut1(x,1,n) << '\n';
        else if(c==2) out << Caut2(x,1,n) << '\n';
    }
}