#include <iostream>
#include <fstream>
#define ll long long
#define MAX INT_MAX

using namespace std;

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

int cautareBinara0(int n, ll a[], int x){

    int st = 0, dr = n-1;

    int poz=-1;

    while(st<=dr){
        int mij = (st+dr)/2;
        if(a[mij] <= x){
            poz = mij;
            st = mij+1;
        }
        else{
            dr = mij-1;
        }
    }

    if(a[poz] == x){
        return poz+1;
    }
    return -1;
}

int cautareBinara1(int n, ll a[], int x){

    int st=0, dr=n-1;
    int poz=-1;
    while(st<=dr){
        int mij = (st+dr)/2;
        if(a[mij] <= x){
            poz = mij;
            st = mij+1;
        }
        else{
            dr = mij-1;
        }
    }
    return poz+1;

}

int cautareBinara2(int n, ll a[], int x){

    int st=0, dr=n-1;
    int poz=-1;
    while(st<=dr){
        int mij = (st+dr)/2;
        if(a[mij] >= x){
            poz = mij;
            dr = mij-1;
        }
        else{
            st = mij+1;
        }
    }
    return poz+1;

}

void solve(int n, ll a[], int k, int x){

    if(k==0){
        g<<cautareBinara0(n, a, x)<<"\n";
        return;
    }
    if(k==1){
        g<<cautareBinara1(n, a, x)<<"\n";
        return;
    }
    if(k==2){
        g<<cautareBinara2(n, a, x)<<"\n";
        return;
    }

}

int main()
{
    int n;
    ll a[100000]={0};

    f>>n;

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

    int m;
    int x, y;
    f>>m;

    while(m--){
        f>>x>>y;
        solve(n, a, x, y);
    }

    return 0;
}