#include <fstream>

using namespace std;

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

long long a[100001], n, m, i, j, x;
short optiune;

int main()
{
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i];

    f >> m;
    for (i = 1; i <= m; i++)
    {
        f >> optiune >> x;
        if (optiune == 0)
        {
          int st = 1, dr = n, m;
          while (st <= dr)
          {
              m = (st+dr)/2;
              if (a[m] <= x)
                st = m+1;
              else
                dr = m-1;
          }
          m = (st+dr)/2;
          if (a[m] > x)
             m--;
          if (a[m] == x)
            g << m << "\n";
          else
            g << -1 << "\n";
        }
        else if (optiune == 1)
        {
            int st = 1, dr = n, m;
          while (st < dr)
          {
              m = (st+dr)/2;
              if (a[m] <= x)
                st = m+1;
              else
                dr = m;
          }
          m = (st+dr)/2;
          if (a[m] > x)
             m--;
            g << m << "\n";
        }
        else if (optiune == 2)
        {
            int st = 1, dr = n, m;
          while (st < dr)
          {
              m = (st+dr)/2;
              if (a[m] < x)
                st = m+1;
              else
                dr = m;
          }
          m = (st+dr)/2;
          if (a[m] < x)
             m++;
          g << m << "\n";
        }
    }
    return 0;
}