#include <fstream>

using namespace std;

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

int n,v[100001],m;

int bynary (int val)
{
    int step,i;
    for (step=1; step<n; step<<=1);
    for (i=0; step; step>>=1)
        if (i+step<n && v[i+step]<=val)
        i=i+step;
    return i;
}

int op1 (int val)
{
    int pos= bynary (val);
    if (v[pos]>v[n] || v[pos]!=val) return -1;
    for (;v[pos]==val; pos++);
    return pos-1;
}

int op2 (int val)
{
    int pos= bynary (val);
    for (;v[pos]<=val && pos<=n ;pos++);
    return pos-1;
}

int op3 (int val)
{
    int pos= bynary (val);
    for (;v[pos]>=val && pos>=1;pos--);
    return pos+1;
}

int main()
{
    int op,x;

    fin>>n;
    for (int i=1;i<=n;i++) fin>>v[i];
    fin>>m;
    for (int i=1;i<=m;i++)
    {
        fin>>op>>x;
        if (op==0) fout<<op1(x);
        else if (op==1) fout<<op2(x);
        else fout<<op3(x);
        fout<<"\n";
    }
}