#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, i, v[100000], m, x, c, mid, l, r, maxi, mini, qp;
int main()
{
    fin >> n >> v[0];
    for (i=1; i<n; i++)
    {
        fin >> v[i];
    }
    fin >> m;
    for (i=0; i<m; i++)
    {
        fin >> c >> x;
        if (c==0)
        {
            l=0;
            r=n-1;
            while (r!=l)
            {
                mid=(l+r+1)/2;
                if (v[mid] <= x) l=mid;
                else r=mid-1;
            }
            if (v[l]==x)
                fout << l+1 << endl;
            else
                fout << -1 << endl;
        }
        if (c==1)
        {
            l=0;
            r=n-1;
            while (r!=l)
            {
                mid=(l+r+1)/2;
                if (v[mid] <= x) l=mid;
                else r=mid-1;
            }
            if (v[l] == x)
                fout << l+1;
            else
            {
                qp=n/2;
                while (v[qp]>=x)
                {
                    qp--;
                    l=0;
                    r=n-1;
                    while (r!=l)
                    {
                        mid=(l+r+1)/2;
                        if (v[mid] <= v[qp]) l=mid;
                        else r=mid-1;
                    }
                }
                fout << l+1;
            }
            if (c==2)
            {
                l=0;
                r=n-1;
                while (r!=l)
                {
                    mid=(l+r+1)/2;
                    if (v[mid] <= x) l=mid;
                    else r=mid-1;
                }
                if (v[l]!=x)
                {
                    qp=n/2;
                    while (v[qp]<x)
                    {
                        qp++;
                        l=0;
                        r=n-1;
                        while (r!=l)
                        {
                            mid=(l+r+1)/2;
                            if (v[mid] <= v[qp]) l=mid;
                            else r=mid-1;
                        }
                        fout << l+1;
                    }
                    fout << l+1;
                }
                if (v[l-1] == x)
                {
                    while(v[l-1]!=x)
                    {
                        l--;
                    }
                }
                if (v[l]==x) fout << l+1;
                fout << endl;
            }
        }
    }
    return 0;
}