#include <fstream>

using namespace std;

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

int n,v[100001],m;

int bynary (int val)
{
    int lo=-1,hi=n;
    while (hi-lo>1)
    {
        int mid=(lo+hi)/2;
        if (v[mid]<val) lo=mid;
        else hi=mid;
    }
    return hi;
}

int op1 (int val)
{
    int pos= bynary (val);
    if (v[pos]!=val || 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";
    }
}