#include <bits/stdc++.h>
using namespace std;
ifstream in("cautbin.in"); ofstream out("cautbin.out");
int v [100001];

int search0 (int right,int target){
    int left=1;int mem,mid; 
    while (left <=right)
         {
           mid= left+(right-left)/2;
           if (v [mid]==target) {mem=mid;left=mid+1;}
           else if (v[mid]<target) left=mid+1; else right=mid-1;
         }
         if (mem)
         return mem; else return -1;
}

int search1 (int right,int target){
    int left=1;int mem,mid; 
    while (left <=right)
         {
           mid= left+(right-left)/2;
           if (v [mid]<=target) { mem=mid; left=mid+1;}
            else right=mid-1;
         }
         return mem;
}

int search2 (int right,int target){
    int left=1;int mem,mid; 
    while (left <=right)
         {
           mid= left+(right-left)/2;
           if (v [mid]>=target) {mem=mid; right=mid-1;}
           else if (v[mid]<target) left=mid+1;
         }
         return mem;
}

int main() {
	int t,k,n,m;
	in>>n;
	for (int i=1;i<=n;++i) in>>v[i];
    in>>m;
    while (m--){
        in>>t>>k;
        if (t==0) out <<search0 (n,k)<<"\n";
        if (t==1) out <<search1 (n,k)<<"\n" ;
        if (t==2) out <<search2 (n,k)<<"\n";
    }
	return 0;
}