#include<fstream>
std::ifstream fin("cautbin.in");
std::ofstream fout("cautbin.out");
int start=1, n, m;
int vec[100001];
void getMax()
{
    for(; start<=n; start<<=1);
}
int binarySearch(int val)
{
    int lg=start;
    int pos=0;
    for(; lg; lg>>=1)
        if(pos+lg<=n && vec[pos+lg]<=val)
            pos+=lg;
    return pos;
}
int secondCase(int val)
{
    int lg=start;
    int pos=n-1;
    for(; lg; lg>>=1)
        if(pos-lg>=0 && vec[pos-lg]>=val)
            pos-=lg;
    return pos;
}
void solveTask(int q, int val)
{
    if(!q)
    {
        int pos= binarySearch(val);
        if(vec[pos]==val)
            fout<<pos+1<<'\n';
        else
            fout<<-1<<'\n';
    }
    else if(q==1)
        fout<<binarySearch(val)+1<<'\n';
    else
        fout<<secondCase(val)+1<<'\n';
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    fin>>n;
    getMax();
    for(int index=0; index<n; ++index)
        fin>>vec[index];
    fin>>m;
    for(int index=0; index<m; ++index)
    {
        int q, val;
        fin>>q>>val;
        solveTask(q, val);
    }
    return 0;
}