#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100001];
int main()
{
    int n,i,x,st,dr,mij,m,op;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    f>>m;
    while(m--)
    {
        f>>op>>x;
        st=1;
        dr=n;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(a[mij]>x)
                dr=mij-1;
            else
                if(a[mij]<=x)
                    st=mij+1;
        }
        if(a[dr]==x)
        {
            if(op<=1)
            {
                while(a[dr]==x)
                    dr++;
                dr--;
                g<<dr;
            }
            else
            {
                while(a[dr]==x)
                    dr--;
                dr++;
                g<<dr;
            }
        }
        else
        {
            if(op==0)
                g<<-1;
            else
            {
                if(op==1)
                    g<<dr;
                else
                {
                    dr++;
                    g<<dr;
                }
            }
        }
        g<<'\n';
    }
    return 0;
}