#include <iostream>
#include <bits/stdc++.h>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int N,M,solv[100005],k,v[100005];
int b0(int st, int dr, int x)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<=x) st=m+1;
        else dr=m-1;
    }
    m=(st+dr)/2;
    if(v[m]>x) m--;
    if(v[m]==x) return m;
    return -1;
}
int b1(int st, int dr, int x)
{
    int m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]<=x)
            st=m+1;
        else dr=m;
    }
    m=(st+dr)/2;
    if(v[m]>x) m--;
    return m;

}
int b2(int st, int dr, int x)
{
    int m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]<x) st=m+1;
        else dr=m;
    }
    m=(st+dr)/2;
    if(v[m]<x) m++;
    return m;
}
int main()
{  int val,tip;
   in>>N;
   for(int i=1; i<=N; ++i)
    in>>v[i];
    in>>M;
   while(M--)
   {
       in>>tip>>val;
       if(tip==0) out<<b0(1,N,val)<<"\n";
       else if(tip==1) out<<b1(1,N,val)<<"\n";
       else out<<b2(1,N,val)<<"\n";
   }
    return 0;
}