#include <stdio.h>

using namespace std;

int v[200000];

int zero(int a,int b,int y)
{
    int m;
    while(a<=b)
    {
               m=(a + b)/2;
               if(v[m]<=y)a=m+1;
                                else b=m-1;
    }
    m=(a+b)/2;
    if(v[m]>y)m--;
    if(v[m]==y)return m;
    return -1;
}


int unu(int a,int b,int y)
{
    int m,n=b;
    while(a<b)
    {
               m=(a+b)/2;
               if(v[m]<=y)a=m+1;
                                else b=m;
    }
    m=(a+b)/2;
    if(v[m]>y)m--;
    return m;
}

int doi(int a,int b,int y)
{   
    int m;
    while(a<b)
    {
              m=(a+b)/2;
              if(v[m]>=y)b=m;
                             else a=m+1;
    }
    m=(a+b)/2;
    if(v[m]<y)m++;
    return m;
}

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