#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
#define MAX_SIZE 100010
int n, m, i, j, c, val, rasp, in, sf, mid;
int v[MAX_SIZE];

void Initializare(){
    in = 1;
    sf = n;
    mid = (in+sf)/2;
    rasp = -1;
}
void SearchLeft() {
    sf = mid;
    mid = (in+sf)/2;
}

void SearchRight() {
    in = mid;
    mid = (in+sf)/2;
}

int Find0(int val) {
    Initializare();
    ///cout << in << ' ' << mid << ' ' << sf << '\n';
    while(in != sf) {
        if(v[mid] == val) {
            if(in != mid) {
                rasp = mid;
                SearchRight();
            }
            else
                SearchLeft();
        } else if(v[mid] < val) {
            if(in != mid)
                SearchRight();
            else
                SearchLeft();
        }
        else if(v[mid] > val)
            SearchLeft();


        ///cout << in << ' ' << mid << ' ' << sf << '\n';
    }
    return rasp;
}

int Find1(int val) {
    Initializare();
    ///cout << in << ' ' << mid << ' ' << sf << '\n';
    while(in != sf) {
        if(v[mid] <= val) {
            rasp = mid;
            if(in != mid)
                SearchRight();
            else {
                mid += 1;
                SearchRight();
                if(v[mid] <= val)
                    rasp = mid;
            }
        } else if(v[mid] > val) {
            if(sf != mid)
                SearchLeft();
            else {
                mid -= 1;
                SearchRight();
            }
        }
        ///cout << in << ' ' << mid << ' ' << sf << '\n';
    }
    return rasp;
}

int Find2(int val) {
    Initializare();
    ///cout << in << ' ' << mid << ' ' << sf << '\n';
    while(in != sf) {
        if(v[mid] >= val) {
            rasp = mid;
            SearchLeft();
        } else if(v[mid] < val) {
            if(in != mid) {
                SearchRight();
            } else {
                mid += 1;
                SearchRight();
                if(v[mid] >= val)
                    rasp = mid;
            }
        }
        ///cout << in << ' ' << mid << ' ' << sf << '\n';
    }
    return rasp;
}

int main()
{
    f >> n;
    for(i = 1; i <= n; i++) {
        f >> v[i];
        ///cout << v[i] << ' ';
    }
    ///cout << '\n';

    f >> m;
    for(i = 1; i <= m; i++) {
        f >> c >> val;
        ///cout << i << '\n';
        if(c == 0)
           rasp = Find0(val);
        else if(c == 1)
            rasp = Find1(val);
        else if(c == 2)
            rasp = Find2(val);


        g << rasp << '\n';
        ///cout << '\n';
    }
    return 0;
}