#include <bits/stdc++.h>

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

int n, m;
int nums[100005];

int binS(int val, int task);

int main()
{

    fin >> n;

    for(int i = 1; i <= n; ++i){
        fin >> nums[i];
    }

    fin >> m;

    while(m--){
        int task, val;
        fin >> task >> val;

        fout << binS(val, task) << "\n";
    }

    return 0;
}

int binS(int val, int task){
    int lft = 1, rgt = n;

    while(rgt - lft > 1){
        int mid = (lft + rgt) / 2;

        if(task < 2){
            if(nums[mid] <= val) lft = mid;
            else rgt = mid;
        }
        else{
            if(nums[mid] >= val) rgt = mid;
            else lft = mid;
        }
    }

    if(!task){
        if(nums[rgt] == val) return rgt;
        else if(nums[lft] == val) return lft;
        else return -1;
    }
    else if(task == 1){
        if(nums[rgt] == val) return rgt;
        else return lft;
    }
    else{
        if(nums[lft] == val) return lft;
        else return rgt;
    }

}