#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int N , i , a ,  b , p , u , m , v[100001] , M;

int main()
{
    f >>  N ;

    for( i = 1 ; i <= N ; i++ )
    {
        f >> v[i];
    }

    f >> M ;

    for( i = 1 ; i <= M ; i++)
    {
        f >> a >> b;
        p=1;
        u=N;
        if ( a == 0 )
        {
              while (p <= u)
                {
                 m = (p + u) / 2;
                 if (v[m] <= b)
                          p = m + 1;
                   else
                          u = m - 1;
                }
             m = (p + u) / 2;

    if (v[m] > b) m --;
    if (v[m] == b) g << m << endl;
           else g << -1 << endl;
        }

        if ( a == 1 )
        {
             while (p < u)
                {
                 m = (p + u) / 2;
                 if (v[m] <= b)
                  p = m + 1;
                 else
                   u = m;
                 }

        m = (p + u) / 2;
        if (v[m] > b) -- m;
     g << m << endl;
        }

        if( a == 2)
        {
            while (p < u)
                {
                 m = (p + u) / 2;
                 if (v[m] < b)
                        p = m + 1;
                   else
                        u = m;
                }

          m = (p + u) / 2;
          if (v[m] < b)
                 ++ m;
         g <<  m << endl;
        }
    }
}