//
//  main.cpp
//  018
//
//  Created by adrian ilisei on 30/06/2018.
//  Copyright © 2018 adrian ilisei. All rights reserved.
//

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m;
long v[100010];

int cautbin(int type, long number, int st, int dr)
{
    if(type == 0)
    {
        if(st == dr)
        {
            if(number == v[st]) return st;
            else return -1;
        }
        if(v[st] == number && v[st+1] > number)
            return st;
        if(dr - st <= 1)
            return -1;
        int half = st/2 + dr/2;
        if(v[half] <= number)
            return cautbin(0, number, half + 1, dr);
        else
            return cautbin(0, number, st, half);
    } else if(type == 1)
    {
        if(st == dr)
        {
            if(v[st] <= number) return st;
            else return -1;
        }
        if(v[st] <= number && v[st+1] > number)
            return st;
        if(dr - st <= 1)
            return -1;
        int half = st/2 + dr/2;
        if(v[half] <= number)
            return cautbin(1, number, half + 1, dr);
        else
            return cautbin(1, number, st, half);
    } else
    {
        if(st == dr)
        {
            if(v[st] >= number) return st;
            else return -1;
        }
        if(v[dr] >= number && v[dr-1] < number)
            return dr;
        if(dr - st <= 1)
            return -1;
        int half = st/2 + dr/2;
        if(v[half] >= number)
            return cautbin(2, number, st, half);
        else
            return cautbin(2, number, half + 1, dr);
    }
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>v[i];
    fin>>m;
    int type;
    long number;
    for(int i=1; i<=m; i++)
    {
        fin>>type>>number;
        fout<<cautbin(type, number, 0, n)<<"\n";
    }
    return 0;
}