#include <bits/stdc++.h>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,logn,v[100001];

int main() {

    f>>n;

    for(int i=1;i<=n;++i) f>>v[i];
    for(logn=1; logn<=n; logn<<=1);

    int T;
    f>>T;

    for(int tip,x;T;--T) {
        f>>tip>>x;

        if(tip<2) {
            int lg,i;

            for(lg=logn,i=0;lg;lg>>=1)
                if(i+lg<=n && v[i+lg]<=x) i+=lg;

            if(!tip && v[i]!=x)
                g<<"-1\n";
            else g<<i<<'\n';
        }
        else {
            int lg,i;

            for(lg=logn,i=n;lg;lg>>=1)
                if(i-lg>0 && v[i-lg]>=x)
                    i-=lg;

            g<<i<<'\n';
        }
    }
    g.close();
    f.close();
    return 0;
}