#include <cstdio>

using namespace std;
int a[100010],n,m,x,q;
int cautare(int x)
{
    int pas,i;
    for(pas=1;pas<n;pas<<=1);
    for(i=0;pas;pas>>=1)
    {
        if(pas+i<n && a[i+pas]<=x)
            i+=pas;
    }
    if(a[i]==x)
        return i;
    else if(q==0)
        return -1;
}
int cautareb(int x)
{
    int pas,i;
    pas=1;
    for(i=n-1;pas<n;pas<<=1)
    {
        if(pas+i>n && a[i-pas]>=x)
            i-=pas;
    }
    if(a[i]==x)
        return i;
    else if(q==0)
        return -1;
}
void citire()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d %d\n",&q,&x);
        if(q==0 || q==1)
            printf("%d\n",cautare(x));
        else
            printf("%d\n",cautareb(x));
    }
}
int main()
{
    citire();
    return 0;
}