#include <iostream>
#include <fstream>
using namespace std;

long binKer_0(long a[], long x, int n)
{
    int bal = 1, jobb = n;

    while (bal < jobb) {
        int k = (bal+jobb+1)/2;

        if(x<a[k]) jobb=k-1;
        else bal = k;
    }

	// bal == jobb

	return a[bal] == x ? bal : -1;
}


int binKer_1(long a[], long x, int n)
{
    int bal=1, jobb=n;

    while(bal<jobb){
        int k = (bal+jobb+1)/2;

        if(a[k]>x) jobb = k-1;
        else bal = k;
    }

    return bal;
}

int binKer_2(long a[], long x, int n)
{
    int bal=1, jobb=n;

    while(bal<jobb){
        int k=(bal+jobb)/2;

        if(a[k]<x) bal = k+1;
        else jobb = k;
    }

    return bal;
}

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    int n, m;
    long x, l;

    in>>n;

    long a[n+1];
    for(int i=1; i<=n; i++) in>>a[i];

    in>>m;
    for(int i=1; i<=m; i++){
        in>>l; in>>x;
        if(l==0) out<<binKer_0(a, x, n)<<endl;
        if(l==1) out<<binKer_1(a, x, n)<<endl;
        if(l==2) out<<binKer_2(a, x, n)<<endl;
    }

    return 0;
}