#include <bits/stdc++.h>

using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

long long v[100005];

int main()
{
    int n,m;
    fin >> n;
    for (int i=1;i<=n;++i){
        fin >> v[i];
    }
    fin >> m;
    for (int i=1;i<=m;++i){
        long long c,x,L = 1, R = n,M;
        fin >> c >> x;
        if (c==0){
            while (L<R){
                M = (L+R)/2;
                if (v[M+1]<=x){
                    L = M+1;
                }else{
                    R = M;
                }
            }
            if (v[L]==x){
                fout << L;
            }else{
                fout << -1;
            }
            fout << '\n';
        }else if (c==2){
            while (L<R){
                M = (L+R)/2;
                if (x<=v[M]){
                    R = M;
                }else{
                    L = M+1;
                }
            }
            fout << L << '\n';
        }else{
            while (L<R){
                M = (L+R)/2;
                if (v[M+1]<=x){
                    L = M+1;
                }else{
                    R = M;
                }
            }
            fout << L << '\n';
        }
    }
    return 0;
}