# include <fstream>
# include <stdio.h>  
using namespace std;
int n, m, a[100005];

int caut0 (int x)
{
    int st=1, dr=n, mid;
    while (st<=dr)
    {
          mid=st+(dr-st)/2;
          if (a[mid]==x)
             return mid;
          else
              if (a[mid]>x)
                 dr=mid-1;
              else
                  st=mid+1;
    }
    return -1;
}
int caut1 (int x)
{
    int st=1, dr=n, mid, w=0;
    while (st<=dr)
    {
          mid=st+(dr-st)/2;
          if (a[mid]<=x)
             w=mid, st=mid+1;
          else
              dr=mid-1;
    }
    return w;
}
int caut2 (int x)
{
    int st=1, dr=n, w=n+1, mid;
    while (st<=dr)
    {
          mid=st+(dr-st)/2;
          if (a[mid]>=x)
            { w=mid; dr=mid-1;}
          else
              st=mid+1;
    }
    return w;
}
int main(void)  
{  
   int i, t, x;  
    
   freopen("cautbin.in", "r", stdin);  
   freopen("cautbin.out", "w", stdout);  
 
   scanf("%d", &n);      
   for (i = 1; i <= n; ++i)  
        scanf("%d", &a[i]);  
           
     scanf("%d", &m);  
     for (; m; --m)  
     {  
         scanf("%d %d", &t, &x);  
         if (!t)  
             printf("%d\n", caut0(x));  
         else if (t == 1)  
             printf("%d\n", caut1(x));  
         else  
             printf("%d\n",  caut2(x));  
     }  
 }