#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n, v[100005], m, t, x;
int bin_search0(int st, int dr, int val)
{
    if(st > dr) return -1;
    int mij=(st+dr)/2;
    if(v[mij] < val) return bin_search0(mij+1, dr, val);
    if(v[mij] > val) return bin_search0(st, mij-1, val);
    if(v[mij] == val && v[mij+1] == val) return bin_search0(mij+1, dr, val);

    return mij;
}

int bin_search1(int st, int dr, int val)
{
    if(st > dr) return -1;
    int mij=(st+dr)/2;
    if(v[mij] <= val && v[mij+1] <= val) return bin_search1(mij+1, dr, val);
    if(v[mij] > val) return bin_search1(st, mij-1, val);

    return mij;
}
int bin_search2(int st, int dr, int val)
{
    if(st > dr) return -1;
    int mij=(st+dr)/2;
    if(v[mij] < val) return bin_search2(mij+1, dr, val);
    if(v[mij] >= val && v[mij-1]>= val) return bin_search2(st, mij-1, val);

    return mij;
}
int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>v[i];
    in>>m;
    for(int k=1; k<=m; k++)
    {
        in>>t>>x;
        if (t == 0) out<<bin_search0(1,n,x)<<'\n';
        if (t == 1) out<<bin_search1(1,n,x)<<'\n';
        if (t == 2) out<<bin_search2(1,n,x)<<'\n';
    }
    return 0;
}