#include <bits/stdc++.h>
using namespace std;
int v[100000];
int bsearch0(int p,int u,int key)
{
    int m; 
    while(p<=u)
    {
        m=(p+u)/2;
        if(v[m]<=key) p=m+1;
        else u=m-1;
    }
    m=(p+u)/2;
    if(v[m]>key)m--;
    if(v[m]==key) return m;
    return -1;
}
int bsearch1(int p,int u,int key)
{
    int m;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<=key) p=m+1;
        else u=m;
    }
    m=(p+u)/2;
    if(v[m]>key) --m;
    return m;

}
int bsearch2(int p,int u,int key)
{
    int m;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<key) p=m+1;
        else u=m;
    }
    m=(p+u)/2;
    if(v[m]<key) ++m;
    return m;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n; cin>>n; 
    for(int i=1;i<=n;i++)
        cin>>v[i];
    int m; cin>>m;int tip,val;
    while(m--)
    {
        cin>>tip>>val;
        if(tip==0) cout<<bsearch0(1,n,val)<<"\n";
        else if(tip==1) cout<<bsearch1(1,n,val)<<"\n";
        else cout<<bsearch2(1,n,val)<<"\n";
    }
    return 0;
}