#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;
    int dr=n-1;
    int mij;
    while(st<=dr){
        mij = st + (dr-st)/2;
        if(x >= a[mij]){
            st = mij + 1;
        }
        else{
            if(x < a[mij])
                dr = mij - 1;
        }
    }
    while(a[mij]>x){
        mij--;
    }
    if(a[mij] == x)
        return mij+1;
    return -1;
}

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

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

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

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

}

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

    if(k==0){
        cout<<cautareBinara0(n, a, x)<<"\n";
        return;
    }
    if(k==1){
        cout<<cautareBinara1(n, a, x)<<"\n";
        return;
    }
    if(k==2){
        cout<<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;
}