#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "cautbin.in"
#define FOUT "cautbin.out"
#define MAX_N 100005

int A[MAX_N];
int N, M;

    int solve (int tp, int el)
    {
        int li = 1, lf = N, m;
        
        int ret = -1;
        if (tp == 0)
        {
               while (li <= lf)
               {
                     m = (li + lf) >> 1;
                     if (A[m] == el) break;
                     
                     if (A[m] < el) li = m + 1;
                        else lf = m - 1;
               }
               if (A[m] != el) return ret;
               while (A[m + 1] == el && m < N) ++m;
               return m;
        }
        if (tp == 1) 
        {
               while (li <= lf)
               {
                     m = (li + lf) >> 1;
                     if (A[m] == el) break;
                     
                     if (A[m] < el) li = m + 1;
                        else lf = m - 1;
               }
               while (A[m + 1] <= el && m < N) ++m;
               while (A[m] > el && m >= 1) --m;
               return m;
        }               
        if (tp == 2) 
        {
               while (li <= lf)
               {
                     m = (li + lf) >> 1;
                     if (A[m] < el) li = m + 1;
                        else lf = m - 1;
               }
               while (A[m - 1] >= el && m > 1) --m;
               while (A[m] < el && m <= N) ++m;
               return m;
        }
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d", &N);
        int i, tp, el;
        
        for (i = 1; i <= N; ++i) scanf ("%d", A + i);
        
        scanf ("%d", &M);
        while (M--)
        {
              scanf ("%d %d", &tp, &el);
              int RES = solve (tp, el);
              
              printf ("%d\n", RES);
        }
        
        return 0;
    }