#include <bits/stdc++.h>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001],N;
int cbin(int val)
{
    int poz=0;
    for(int msk=1<<20; msk>0; msk/=2)
        if(poz+msk<=N && v[poz+msk]<=val)
            poz+=msk;
    if(v[poz]==val)
        return poz;
    else
        return -1;
}

int cbin2(int val)
{
    int poz=0;
    for(int msk=1<<20; msk>0; msk/=2)
        if(poz+msk<=N && v[poz+msk]<=val)
            poz+=msk;
        return poz;

}

int cbin3(int val)
{
    int poz=0;
    for(int msk=1<<20; msk>0; msk/=2)
        if(poz+msk<=N && v[poz+msk]<val)
            poz+=msk;
        return poz + 1;

}

int main()
{
    int M,i,c,x;
    in>>N;
    for(i=1; i<=N; i++)
    {
        in>>v[i];
    }
    in>>M;
    for(i=1; i<=M; i++)
    {
        in>>c>>x;
        if(c==0)
        {
            out<<cbin(x)<<'\n';
        }
        else if(c==1)
        {
            out<<cbin2(x)<<'\n';
        }
        else if(c==2)
        {
            out<<cbin3(x)<<'\n';
        }
    }
    return 0;
}