#include <stdio.h>
#define MAX 100000
int v[MAX];

    int cautare_binara(int x,int mod,int n){
    int step,i;

    if(mod == 0){

    for(step = 1;step < n;step <<= 1);
        for(i = 0 ;step;step >>= 1)
            {if(i + step < n && v[i + step] <= x)
                i = i + step;

            if(v[i] == x)
            return i;}

            return -1;
    }
    else
    if(mod == 1){

    for(step = 1;step < n;step = step << 1);
        for(i = 0 ;step;step = step >> 1)
            if(i + step < n && v[i + step] <= x)
                i = i + step;

        return i;
    }
    else{

        for(step = 1;step < n;step = step << 1);
             for(i = 0 ;step;step = step >> 1)
                if(i + step < n && v[i + step] < x)
                i = i + step;

        return i + 1;

    }
    }

int main()

{
    int n,m,i,j,mod,x,step,gasit;

    FILE *f,*g;

    f=fopen("cautbin.in","r");
    g=fopen("cautbin.out","w+");

    fscanf(f,"%d",&n);

    for(i = 1;i <= n; ++i)
        fscanf(f,"%d",&v[i]);

    fscanf(f,"%d",&m);

    for(j = 1;j <= m; ++j){

        fscanf(f,"%d %d",&mod,&x);

        fprintf(g,"%d\n",cautare_binara(x,mod,n));



    }




}