//Dragan Andrei Gabriel - Grupa 131
//Cautare binara

#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#define nmax 100001
using namespace std;

int n,m,x,y,v[nmax];

int caut_binar_1(int st,int dr,int val)
{
    int poz=1,putere=(1<<17);  //2^16 < nmax < 2^17
    while(putere>>=1)
        if(poz+putere<=n && v[poz+putere]<=val)
            poz+=putere;
    if (v[poz]==val) return poz;
    return -1;
}

int caut_binar_2(int st,int dr,int val)
{
    int poz=1,putere=(1<<17);
    while(putere>>=1)
        if(poz+putere<=n && v[poz+putere]<=val)
            poz+=putere;
    return poz;
}

int caut_binar_3(int st,int dr,int val)
{
    int poz=1,putere=(1<<17);
    while(putere>>=1)
        if(poz+putere<=n && v[poz+putere]<val)
            poz+=putere;
    if(v[poz]<val) return poz+1;
    return poz;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        if (x==0)
            printf("%d\n",caut_binar_1(1,n,y));
        if (x==1)
            printf("%d\n",caut_binar_2(1,n,y));
        if (x==2)
            printf("%d\n",caut_binar_3(1,n,y));
    }
    return 0;
}