#include <bits/stdc++.h>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,q,v[100200],op,x;

int32_t main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>v[i];
    f>>q;
    for(int i=1; i<=q; i++)
    {
        f>>op>>x;
        int st=1, dr=n, sol=-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(v[mij]<=x)
                st=mij+1, sol=mij;
            else
                dr=mij-1;
        }
        if(op==0)
            if(v[sol]==x)
                g<<sol<<'\n';
            else
                g<<-1<<'\n';
        if(op==1)
            g<<sol<<'\n';
        st=1, dr=n, sol=-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(v[mij]>=x)
                dr=mij-1, sol=mij;
            else
                st=mij+1;
        }
        if(op==2)
            g<<sol<<'\n';
    }
    return 0;
}