#include <fstream>
#include <stdlib.h>
using namespace std;
ifstream fin ("cautbin.in");
ofstream  fout("cautbin.out");
int *v;
int binary( int st, int dr, int piv, int x)
{
    if(v[piv] == x || st >= dr) return piv;
    if(v[piv] > x) return binary( st,  piv-1, (st+piv-1)/2, x);
    else return binary( piv+1, dr, (piv+1+dr)/2, x);
}
int main()
{
    int n, m, i, x, y, poz;
    fin >> n ;
    v = (int *)  calloc(n+1, sizeof(int));
    for( i = 1; i <= n; i++)
        fin >> v[i];
    fin >> m;
    for(i = 0; i < m; i++)
    {
        fin >> x >> y;
        poz = binary(1,n, (n+1)/2, y);


        if( x == 0)
        {
             if(v[poz] != y)
            fout << "-1 ";
            else
            while(v[poz] == y) poz++;
            if(v[poz-1] == y ) fout <<poz-1 << " ";
        }
        else if( x == 1)
        {
            if(v[poz] <= y) while(v[poz] == v[poz+1]) poz++;
            else poz--;
            fout << poz << " ";
        }
        else
        {
             if(v[poz] >= y) while(v[poz] == v[poz-1]) poz--;
            else poz++;
            fout << poz << " ";
        }

    }
    return 0;
}