#include <bits/stdc++.h>

using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");
int i, n, v[100006], gasit, mij, pi, pj, x, m, intr;
int caut(int pi,int pj,int x)
{
    while( pi <= pj && gasit == 0)
    {
        mij = ( pi+pj ) /2;
        if( v[mij] == x){
                gasit = 1;
                return mij;
        }
        else
        {
            if( v[mij] < x )
            {
                pi = mij + 1;
            }
            else
            {
                pj = mij-1;
            }
        }
    }
    return mij;
}
void intrebari(int p,int poz)
{
    if( p == 0){
            if(v[poz] != x)
                g << -1 << "\n";
            else{
                while(v[poz + 1] == x)
                    poz++;
                g << poz <<"\n";
            }
        }
        if(p == 1){
                if(v[poz] == x)
                while(v[poz + 1] == x)
                    poz++;
                  else{
                    poz = caut(1,n,x - 1);
                     while(v[poz] > x)
                        poz--;
                     while(v[poz + 1] == v[poz])
                      poz++;
                  }
                    g << poz <<"\n";

        }
        if(p == 2){
            if(v[poz] == x)
                  while(v[poz - 1] == x)
                    poz--;
            else{
                 poz = caut(1,n,x + 1);
                 while(v[poz] < x)
                    poz++;
                while(v[poz - 1] == v[poz])
                    poz--;
             }

        g << poz << "\n";
        }
}
int main()
{
    f >> n;
    for( i = 1; i <= n; i++)
        f >> v[i];
    f >> m;
    while(m>0)
    {
        gasit = 0;
        f >> intr >> x;
        mij=caut(1,n,x);
        intrebari(intr,mij);
        m--;
    }
    return 0;
}