#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    int n;
    int v[100005];
    f>>n;
    for(int i = 1; i <= n; i++)
        f>>v[i];
    int T;
    f>>T;
    while(T--)
    {
        int p,x;
        f>>p>>x;
        int st = 0, dr = n+1;
          int poz = -1;
        if(p == 0)
        {

          while(st <= dr)
          {
              int m = st +(dr-st)/2;
            if(v[m] > x)
                dr = m-1;
            else
            {
                if(v[m] == x)
                    poz = m;
                st = m + 1;
            }

          }


        }
        if(p == 1)
        {
           while(st <= dr)
           {
               int m = st + (dr-st)/2;
               if(v[m] <= x)
              {
                  st = m + 1;
                  poz = m;
              }
              else
                dr = m-1;


           }


        }
        if(p == 2)
        {
           while(st <= dr)
           {
               int m = st + (dr-st)/2;
               if(v[m] >= x)
                poz = m,dr = m-1;
               else
                st = m+1;
           }


        }

        g<<poz<<"\n";
    }
    return 0;
}