#include <iostream>
#include <fstream>
#define MAX 100001

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,v[MAX],i,tip,val,t;

int c_bin_0(int first,int last,int val){
    int m;
    while(first<=last){
        m=(first+last)/2;
        if(v[m]<=val)
            first=m+1;
        else
            last=m-1;}
    m=(first+last)/2;
    if(v[m]>val)
        m--;
    if(v[m]==val)
        return m;
    return -1;}

int c_bin_1(int first,int last,int val){
    int m;
    while(first<last){
        m=(first+last)/2;
        if(v[m]<=val)
            first=m+1;
        else
            last=m;}
    m=(first+last)/2;
    if(v[m]>val)
         --m;
    return m;}

int c_bin_2(int first,int last,int val){
    int m;
    while(first<last){
        m=(first+last)/2;
        if(v[m]<val)
            first=m+1;
        else
            last=m;}
    m=(first+last)/2;
    if(v[m]<val)
         ++m;
    return m;}

int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
       fin>>v[i];
    fin>>t;
    for(i=1;i<=t;++i)
    {
        fin>>tip>>val;
        if(tip==0) fout<<c_bin_0(1,n,val)<<"\n";
        if(tip==1) fout<<c_bin_1(1,n,val)<<"\n";
        if(tip==2) fout<<c_bin_2(1,n,val)<<"\n";
    }
    return 0;
}