#include<stdlib.h> 
#include<stdio.h>
  
int v[100000]; 
int intr0 (int p, int u, int b)
 { int m;     
   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) return m; 
   return -1;} 
 
int intr1 (int p, int u, int b)
 { int m, n = u; 
   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;
   return m; }
 
 int intr2 (int p, int u, int b)
  { int m;    
    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; 
    return m; } 
 
 int main () 
 {int i, n, m,a,b;    
freopen("cautbin.in","r",stdin); 

freopen("cautbin.out","w",stdout); 
    
scanf("%d", &n); 
    
for (i = 1; i <= n; ++ i) 
        
scanf("%d", &v[i]); 
     
 
    
scanf("%d", &m); 
 
 
    
while (m --){ 
         
scanf("%d%d", &a, &b); 
          
if ( a== 0)
             
printf("%d\n", intr0(1, n, b)); 
          
if (a == 1) 
            
printf("%d\n", intr1(1, n, b)); 
          
if (a == 2) 
             
printf("%d\n", intr2(1, n, b)); 
    
} 
    
exit(0); 
}