#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#define pb push_back
#define maxn 100050
using namespace std;
int a[maxn],n,m,x,y,i;

int bsearch0(int key)
{
    int st=1,dr=n,m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(a[m]<=key)
            st=m+1;
        else
            dr=m-1;
    }
    if(a[m]>key) --m;
    if(a[m]==key)
        return m;
    return -1;
}

int bsearch1(int key)
{
    int st=1,dr=n,m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(a[m]<=key)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if(a[m]>key) --m;
    if(a[m]==key)
        return m;
}

int bsearch2(int key)
{
    int st=1,dr=n,m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(a[m]<key)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if(a[m]<key) ++m;
    if(a[m]==key)
        return m;
}

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