#include <fstream>
using namespace std;
ifstream f ("cautarebin.in");
ofstream g ("cautarebin.out");
int a[100005], b[100005][5];
int cautarebinara0(int l, int r, int y)
{
    int m;
    if(l==r) if(y==a[l]) return l;
    else return -1;

    else
    {
        m=(l+r+1)/2;
        if(y>=a[m]) return cautarebinara0(m, r, y);
        else return cautarebinara0(l, m-1, y);
    }
}
int cautarebinara1(int l, int r, int y)
{
    int m;
    if(l==r) return l;
    else
    {
        m=(l+r+1)/2;
        if(a[m]<=y)
        {
            return cautarebinara1(m, r, y);
        }
        else return cautarebinara1(l, m-1, y);
    }
}
int cautarebinara2(int l, int r, int y)
{
    int m;
    if(l==r) return l;
    else
    {
        m=(l+r)/2;
        if(a[m]>=y)
        {
            return cautarebinara2(l, m, y);
        }
        else return cautarebinara2(m+1, r, y);
    }
}
int main()
{
    int n, i, m, y, x;
    f>>n;
    for(i=1; i<=n; i++)
        f>>a[i];
    f>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        if(x==0)
        {
            g<<cautarebinara0(1, n, y)<<"\n";
        }
        if(x==1)
        {
            g<<cautarebinara1(1, n, y)<<"\n" ;
        }
        if(x==2)
        {

            g<<cautarebinara2(1, n, y)<<"\n";
        }
    }
    return 0;
}