#include <fstream>

using namespace std;
int v[100005],x[100005],f[100005];
int main()
{
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    int n;
    fin>>n;
    int i,j;
    for (i=0;i<n;i++) {
        fin>>v[i];
    }
    int m,nr,d,s,g;
    bool ok=0;
    fin>>m;
    for (i=0;i<m;i++) {
        fin>>f[i]>>x[i];
        }
        for (i=0;i<m;i++) {
        if (f[i]==0) {
        s=0;
        d=n-1;
        ok=0;
        while (ok==0&&d>=s) {
            g=(s+d)/2;
            if (v[g]==x[i]) {
                ok=1;
            }
            else if (v[g]<x[i]) {
                    s=g+1;
                }
                else {
                    d=g-1;
                }
            }
            if (ok==1) {
                for (j=g+1;j<n&&ok==1;j++) {
                    if (v[j]!=x[i]) {
                        ok=0;
                    }
                }
                fout<<j-1<<"\n";
            }
            else {
                fout<<-1<<"\n";
            }
        }

        else if (f[i]==1) {
            s=0;
        d=n-1;
        ok=0;
        while (ok==0&&d>=s) {
            g=(s+d)/2;
            if (v[g]==x[i]) {
                ok=1;
            }
            else if (v[g]<x[i]) {
                    s=g+1;
                }
                else {
                    d=g-1;
                }
            }
            if (ok==1) {
                for (j=g;j<n&&ok==1;j++) {
                    if (v[j]>x[i]) {
                        ok=0;
                    }
                }
                fout<<j-1<<"\n";
            }
            else {
                fout<<g-1<<"\n";
            }
        }
        else if (f[i]==2){
        s=0;
        d=n-1;
        ok=0;
        while (ok==0&&d>=s) {
            g=(s+d)/2;
            if (v[g]==x[i]) {
                ok=1;
            }
            else if (v[g]<x[i]) {
                    s=g+1;
                }
                else {
                    d=g-1;
                }
            }
            if (ok==1) {
                for (j=g-1;j>=0&&ok==1;j--) {
                    if (v[j]<x[i]) {
                        ok=0;
                    }
                }
                fout<<j+3<<"\n";
            }
            else {
                fout<<g<<"\n";
            }
        }
        }
    return 0;
}