#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[100005];

int binsearch0(int st,int dr,int val){
    int mid,sol = 0;
    while(st <= dr){
        mid = (st+dr)/2;
        if(val < v[mid]){
            dr = mid-1;
        }else if(val > v[mid]){
            st = mid+1;
        }else if(val == v[mid]){
            sol = max(sol,mid);
            st = mid+1;
        }
    }
    if(sol == 0){
        return -1;
    }
    return sol;
}

int binsearch1(int st,int dr,int val){
    int mid,sol = 0;
    while(st <= dr){
        mid = (st+dr)/2;
        if(v[mid] <= val){
            sol = max(sol,mid);
            st = mid+1;
        }else if(v[mid] > val){
            dr = mid-1;
        }
    }
    return sol;
}

int binsearch2(int st,int dr,int val){
    int mid,sol = 100000000;
    while(st <= dr){
        mid = (st+dr)/2;
        if(v[mid] < val){
            st = mid+1;
        }else if(v[mid] >= val){
            sol = min(sol,mid);
            dr = mid-1;
        }
    }
    return sol;
}

int main()
{
    int n,i,m,c,a;
    fin>>n;
    for(i = 1; i <= n; i++){
        fin>>v[i];
    }
    fin>>m;
    for(i = 1; i <= m; i++){
        fin>>c>>a;
        if(c == 0){
            fout<<binsearch0(1,n,a)<<'\n';
        }else if(c == 1){
            fout<<binsearch1(1,n,a)<<'\n';
        }else if(c == 2){
            fout<<binsearch2(1,n,a)<<'\n';
        }
    }
    return 0;
}