#include <iostream>
#include <fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n, m;
int * arr;

int cbin0(int x){

    int poz = 0;

    for(int i = (1 << 30); i > 0; i >>= 1){

        if(poz + i < n && arr[poz + i] <= x){

            poz += i;
        }
    }

    if(arr[poz] == x){

        return poz;
    }
    return -1;
}

int cbin1(int x){

    int poz = 0;

    for(int i = (1 << 30); i > 0; i >>= 1){

        if(poz + i < n && arr[poz + i] <= x){

            poz += i;
        }
    }
    return poz;
}

int cbin2(int x){

   int poz = n - 1;

    for(int i = (1 << 30); i > 0; i >>= 1){

        if(poz - i >= 0 && -arr[poz - i] <= -x){

            poz -= i;
        }
    }
    return poz;
}

int main(){

    f >> n;

    arr = new int[n];

    for(int i = 0; i < n; i++){

        f >> arr[i];
    }

    int q, x;

    f >> m;

    for(int tst = 0; tst < m; tst++){

        f >> q >> x;

        if(q == 0){

            g << cbin0(x) + 1 << '\n';
        }
        else if(q == 1){

            g << cbin1(x) + 1 << '\n';
        }
        else{

            g << cbin2(x) + 1 << '\n';
        }
    }

    return 0;
}