#include<stdio.h>
#define maxn 100001
using namespace std;

int n, v[maxn], m, choice, x;

int c0(int value, int low, int high)
{int mid;
while(low<=high)
     {mid=low+(high-low)/2;
      if(v[mid]==value)
        if(v[mid+1]!=value) 
          return mid+1;
      if(v[mid]>value)
        high=mid-1;
      else low=mid+1; 
     }  
return -1;
}

int c1(int value, int low, int high)
{int mid;
while(low<high)
     {mid=low+(high-low)/2;
      if(v[mid]<=value)
        low=mid+1;
      else high=mid-1; 
     }
mid=low+(high-low)/2;
if(v[mid]>value)
  mid--;     
return mid+1;          
}

int c2(int value, int low, int high)
{int mid;
while(low<high)
     {mid=low+(high-low)/2;
      if(v[mid]>=value)
        high=mid-1;
      else low=mid+1;
     } 
mid=low+(high-low)/2;
if(v[mid]<value)
  mid++;     
return mid+1;          
}

int main()
{freopen("cautbin.in", "r", stdin);
freopen("cautbin.out", "w", stdout);

scanf("%d", &n);
for(int j=0; j<n; j++)
   scanf("%d", &v[j]);   

scanf("%d", &m);
for(int j=0; j<m; j++)
   {scanf("%d%d", &choice, &x);
    if(choice==0)
      printf("%d\n", c0(x, 0, n-1));
    else if(choice==1)
           printf("%d\n", c1(x, 0, n-1));
         else printf("%d\n", c2(x, 0, n-1));    
   }

return 0;
}