#include<bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in"); ofstream g("cautbin.out");
int v[100001];
int cb0(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(key<v[m]) --m;
    if(key==v[m]) return m;
    return -1;
}
int cb1(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(key<v[m]) --m;
    return m;
}
int cb2(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 ()
{   int n,T,tip,val;
    f>>n;
    for(int i=1;i<=n;++i) f>>v[i];
    f>>T;
    while(T--)
	{   f>>tip>>val;
		if(tip==0) g<<cb0(1,n,val)<<'\n';
		if(tip==1) g<<cb1(1,n,val)<<'\n';
		if(tip==2) g<<cb2(1,n,val)<<'\n';
    }
    g.close(); return 0;
}