#include <iostream>
#define N_MAX 100000
using namespace std;

int v[N_MAX],x,n;

int c1() {
    int st=1,dr=n,mij,poz=-1;
    while(st<=dr) {
        mij=(st+dr)/2;
        if(v[mij]==x) {
              poz=mij;
              st=mij+1;
        }
        else if(v[mij]<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return poz;
}


int c2() {
    int st=1,dr=n,mij,poz=-1;
    while(st<=dr) {
        mij=(st+dr)/2;
        if(v[mij]<=x) {
              poz=mij;
              st=mij+1;
        }
        else
            dr=mij-1;
    }
    return poz;
}


int c3() {
    int st=1,dr=n,mij,poz=-1;
    while(st<=dr) {
        mij=(st+dr)/2;
        if(v[mij]>=x) {
              poz=mij;
              dr=mij-1;
        }
        else
            st=mij+1;
    }
    return poz;
}


int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int m,i,r;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(i=0;i<m;i++) {
        scanf("%d%d",&r,&x);
        if(r==0) r=c1();
        else if(r==1) r=c2();
        else r=c3();
        cout<<r<<'\n';
    }


    return 0;
}