#include<iostream>
#include<fstream>
#include<vector>
#define MAX_VAL 100001
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m;
vector<int> v;
int search0(int l,int r, int val)
{
    if(l > r) return -1;
    int mid = l+((r-l)/2);
    int max_pos_l = -1;
    int max_pos_r = -1;
    int max_pos_n = -1;
    if(val < v[mid]) max_pos_l = search0(l,mid-1,val);
    else max_pos_r = search0(mid+1,r,val);
    if(v[mid] == val) max_pos_n = mid;
    int max_pos_s = max(max_pos_l,max_pos_r);
    return max(max_pos_n,max_pos_s);
}
int search1(int l,int r,int val)
{
    if(l > r) return -1;
    int mid = l+((r-l)/2);
    int max_pos_l = -1;
    int max_pos_r = -1;
    int max_pos_n = -1;
    if(val < v[mid]) max_pos_l = search0(l,mid-1,val);
    else max_pos_r = search0(mid+1,r,val);
    if(v[mid] <= val) max_pos_n = mid;
    int max_pos_s = max(max_pos_l,max_pos_r);
    return max(max_pos_n,max_pos_s);
}
int search2(int l,int r,int val)
{
    if(l > r) return -1;
    int mid = l+((r-l)/2);
    int max_pos_l = MAX_VAL;
    int max_pos_r = MAX_VAL;
    int max_pos_n = MAX_VAL;
    if(val > v[mid]) max_pos_r = search0(mid+1,r,val);
    else max_pos_l = search0(l,mid-1,val);
    if(v[mid] >= val) max_pos_n = mid;
    int max_pos_s = min(max_pos_l,max_pos_r);
    return min(max_pos_n,max_pos_s);
}
int main()
{
    fin>>n;
    for(int i=0;i<n;i++)
    {
        int k;
        fin>>k;
        v.push_back(k);
    }
    fin>>m;
    for(int i=0;i<m;i++)
    {
        int k1,k2;
        fin>>k1>>k2;
        if(k1 == 0) fout<<search0(0,n-1,k2)+1<<"\n";
        if(k1 == 1) fout<<search1(0,n-1,k2)+1<<"\n";
        if(k1 == 2) fout<<search2(0,n-1,k2)+1<<"\n";
    }
}