#include <iostream>
	
#include <fstream>
	
#include <assert.h>
	
 
	
using namespace std;
	
 
	
#define dim 100010
	
 
	
ifstream fi("cautbin.in");
	
ofstream fo("cautbin.out");
	
 
	
long int a[dim];
	
long int n,m;
	
long int x;
	
 
	
void cit()
	
{
	
    fi>>n;
	
 
	
    for(long int i=1;i<=n;i++)
	
        fi>>a[i];
	
 
	
    fi>>m;
	
}
	
 
	
long int cb0()
	
{
	
    long int s,f,m;
	
 
	
    s=1;
	
    f=n;
	
 
	
    while(s<=f)
	
    {
	
        m=(s+f)/2;
	
 
	
        if(a[m]<=x)
	
            s=m+1;
	
        else
	
            f=m-1;
	
    }
	
 
	
    m=(s+f)/2;
	
 
	
    if(a[m]>x)
	
        m--;
	
 
	
    if(a[m]==x)
	
        return m;
	
 
	
    return -1;
	
 
	
}
	
 
	
long int cb1()
	
{
	
    long int s,f,m;
	
 
	
    s=1;
	
    f=n;
	
 
	
    while(s<f)
	
    {
	
        m=(s+f)/2;
	
 
	
        if(a[m]<=x)
	
            s=m+1;
	
        else
	
            f=m;
	
    }
	
 
	
    m=(s+f)/2;
	
 
	
    if(a[m]>x)
	
        m--;
	
 
	
    return m;
	
}
	
 
	
long int cb2()
	
{
	
    long int s,f,m;
	
 
	
    s=1;
	
    f=n;
	
 
	
    while(s<f)
	
    {
	
        m=(s+f)/2;
	
 
	
        if(a[m]<x)
	
            s=m+1;
	
        else
	
            f=m;
	
    }
	
 
	
    m=(s+f)/2;
	
 
	
    if(a[m]<x)
	
        m++;
	
 
	
    return m;
	
}
	
 
	
int main()
	
{
	
    cit();
	
 
	
    int t;
	
 
	
    for(long int i=1;i<=m;i++)
	
        {fi>>t>>x;
	
        switch(t)
	
            {case 0:
	
                {fo<<cb0();
	
                fo<<'\n';
	
                break;}
	
            case 1:
	
                {fo<<cb1();
	
                fo<<'\n';
	
                break;}
	
            case 2:
	
                {fo<<cb2();
	
                fo<<'\n';
	
                break;}
	
        }}
	
 
	
    return 0;
	
}