#include <bits/stdc++.h>

using namespace std;

int binarySearch1(int arr[], int Size, int st, int dr, int x){

    if( st > dr ){

        if(st >= Size){
            return -1;
        }

        return st;
    }


    int mid = st + (dr - st)/2;

    if(arr[mid] <= x){
        return binarySearch1(arr, Size, mid + 1, dr, x);
    }
    if(arr[mid] > x){
        return binarySearch1(arr, Size, st, mid - 1, x);
    }

    return -1;
}

int binarySearch2(int arr[], int Size, int st, int dr, int x){
    if( st > dr ){

        if(st > Size){
            return -1;
        }

        return st + 1;
    }

    int mid = st + (dr - st)/2;

    if(arr[mid] >= x){
        return binarySearch2(arr, Size, st, mid - 1, x);
    }
    if(arr[mid] < x){
        return binarySearch2(arr, Size, mid + 1, dr, x);
    }

    return -1;
}

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    int n, m, arr[100010];
    in>>n;

    for(int i = 0; i < n; i++){
        in>>arr[i];
    }

    int x, q;

    in>>m;
    for(int i = 0; i < m; i++){
        in>>q>>x;
        if(q == 0 || q == 1){
            out<<binarySearch1(arr, n, 0, n-1, x)<<"\n";
        } else {
            out<<binarySearch2(arr, n, 0, n-1, x) + 1<<"\n";
        }
    }

    return 0;
}