#include <fstream>
#include <stdio.h>

using namespace std;

int n,i,m,j, st, dr, mij;
unsigned int v[200010];
int opt, val;
FILE *fin;
FILE *fout;

void opt0(int val)
{
    st = 0;
    dr = n-1;
    while (st<=dr)
    {
        mij = st + (dr-st) /2;
        if (v[mij]==val)
        {
            if (mij == n-1)
            {
                fprintf(fout, "%d\n", mij+1);
                return;
            }
            else
                if (v[mij+1]!=val)
                {
                    fprintf(fout, "%d\n", mij+1);
                    return;
                }
                else
                    st = mij+1;
        }
        else
        {
            if (val < v[mij])
                dr = mij-1;
            else
                st = mij+1;
        }
    }
    fprintf(fout, "%d\n", -1);
}

void opt1(int val)
{
    st = 0;
    dr = n-1;
    while (st<=dr)
    {
        mij = st + (dr-st) /2;
        if (v[mij]==val)
        {
            if (mij == n-1)
            {
                fprintf(fout, "%d\n", mij+1);
                return;
            }
            else
                if (v[mij+1]!=val)
                {
                    fprintf(fout, "%d\n", mij+1);
                    return;
                }
                else
                    st = mij+1;
        }
        else
        {
            if (v[mij]< val && v[mij+1] > val)
            {
                fprintf(fout, "%d\n", mij+1);
                return;
            }
            if (val < v[mij])
                dr = mij-1;
            else
                st = mij+1;
        }
    }

}

void opt2(int val)
{
        st = 0;
    dr = n-1;
    while (st<=dr)
    {
        mij = st + (dr-st) /2;
        if (v[mij]==val)
        {
            if (mij == 0)
            {
                fprintf(fout, "%d\n", 1);
                return;
            }
            else
                if (v[mij-1]!=val)
                {
                    fprintf(fout, "%d\n", mij+1);
                    return;
                }
                else
                    dr = mij-1;
        }
        else
        {
            if (v[mij] < val && v[mij-1] > val)
            {
                fprintf(fout, "%d\n", mij+2);
                return;
            }
            if (val < v[mij])
                dr = mij-1;
            else
                st = mij+1;
        }
    }
}

int main()
{
    fin = fopen("cautbin.in","r");
    fout = fopen("cautbin.out", "w");

    fscanf(fin, "%d", &n);
    for (i=0;i<n;i++)
        fscanf(fin,"%u ", &v[i]);

    fscanf(fin, "%d", &m);

    for (j=0;j<m;j++)
    {
        fscanf(fin, "%d %d", &opt, &val);
        switch(opt)
        {
            case 0: opt0(val); break;
            case 1: opt1(val); break;
            case 2: opt2(val); break;
            default : break;
        }
    }

    fclose(fin);
    fclose(fout);
}