#include <fstream>

using namespace std;

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

int v[100001];

int caut_bin(int val,int st, int dp) {
    int ans=-1;
    while (st<=dp) {
        int med=(st+dp)/2;
        if (v[med]<=val) {
            ans=med;
            st=med+1;
        } else {
            dp=med-1;
        }
    }
    return ans;
}

int main () {
    int n,m,i,x,y;

    fin >> n;

    for (i=1;i<=n;i++) {
        fin >> v[i];
    }
    
    fin >> m;

    while(m) {
        fin >> x >> y;
        int ans=caut_bin(y,1,n);
        if (x==0) {
            while (v[ans]==v[ans+1]) {
                ans++;
            }
        } else if (x==1) {
            if (v[ans]!=y) {
                while (v[ans+1]<y) {
                    ans++;
                }
            } else {
                while (v[ans]==v[ans+1]) {
                    ans++;
                }
            }
        } else {
            if (v[ans]!=y) {
                if (v[ans]>y) {
                    while (v[ans-1]>y) {
                        ans--;
                    }
                } else {
                    while (v[ans+1]<y) {
                        ans++;
                    }
                }
                ans++;
            } else {
                while (v[ans]==v[ans-1]) {
                    ans--;
                }
            }
        }
        fout << ans << endl;
        m--;
    }
}