#include <fstream>
#define dim 100001
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int binara (int[],int,int,int);
int main()
{
    int v[dim],n,i,caz,x,m,poz;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for (i=0;i<m;i++)
    {
        fin>>caz>>x;

        switch (caz)
        {
            case 0:
                poz=binara(v,1,n,x);
                if(poz==-1)
                    fout<<"-1\n";
                else
                {
                    poz++;
                    while (v[poz]==x&&poz<n)
                        poz++;
                    fout<<poz-1<<"\n";
                }
            break;
            case 1:
                poz=binara(v,1,n,x);
                if(poz==-1)
                {
                    x--;
                    poz=binara(v,1,n,x);
                    while(poz==-1)
                    {
                        x--;
                        poz=binara(v,1,n,x);
                    }
                    poz++;
                    while(v[poz]==x&&poz<n)
                        poz++;
                    fout<<poz-1<<"\n";
                }
                else
                {
                    poz++;
                    while (v[poz]==x&&poz<n)
                        poz++;
                    fout<<poz-1<<"\n";
                }
            break;
            case 2:
                poz=binara (v,1,n,x);
                if (poz==-1)
                {
                    x++;
                    poz=binara(v,1,n,x);
                    while (poz==-1)
                    {
                        x++;
                        poz=binara(v,1,n,x);
                    }
                    poz--;
                    while (v[poz]==x&&poz)
                        poz--;
                    fout<<poz+1<<"\n";
                }
                else
                {
                    poz--;
                    while (v[poz]==x&&poz )
                        poz--;
                    fout<<poz+1<<"\n";
                }
            break;
        }
    }
    //rez=binara (v,0,n-1,5);
//    fout<<rez;
    return 0;
}


int binara ( int v[dim],int a,int b,int x)
{
    int mijl;
    mijl=a+(b-a)/2;
    if(a<=b)
    {
        if ( x>v[mijl])
            return binara (v,mijl+1,b,x);
        else
            if (x<v[mijl])
                return binara(v,a,mijl-1,x);
            else
                return mijl;
    }
    else
        return -1;
}