#include <fstream>

using namespace std;

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