#include <fstream>
#include <iostream>
#define DIM 100001
using namespace std;

int n,v[DIM],pos;

int findVal1(int l,int r,int x) {
    if(l>r)
        return r;
    int mid=(l+r)/2;
    if(v[mid]==x)
        pos=mid;
    if(v[mid]>=x)
        return findVal1(l,mid-1,x);
    return findVal1(mid+1,r,x);
}

int findVal(int l,int r,int x) {
    if(l>r)
        return l;
    int mid=(l+r)/2;
    if(v[mid]==x)
        pos=mid;
    if(v[mid]<=x)
        return findVal(mid+1,r,x);
    return findVal(l,mid-1,x);
}

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    int m,a,b,c;
    fin>>m;
    for(int i=1;i<=m;i++) {
        fin>>a>>b;
        pos=-1;
        if(a<2)
            c=findVal(1,n,b);
        else
            c=findVal1(1,n,b);
        if(a==0||pos>0)
            fout<<pos<<'\n';
        else
            fout<<c<<'\n';
    }
    return 0;
}