#include<bits/stdc++.h>

using namespace std;

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

int a[100100],n,m,mid,x,y;

int binarySearch1(int i, int n, int x){
    if (n>=1){
        mid = (i+n)/2;
        if (a[mid] == x){
            while(a[mid] == a[mid+1])
                mid++;
            return mid;
        }

        if (a[mid]>x)
            return binarySearch1(1,mid-1,x);

        return binarySearch1(mid+1,n,x);
    }
    return -1;
}

int binarySearch2(int i, int n, int x){
    if (n>=1){
        mid = (i+n)/2;
        if (a[mid] == x){
            while(a[mid] == a[mid-1])
                mid--;
            return mid;
        }

        if (a[mid]>x)
            return binarySearch2(1,mid-1,x);

        return binarySearch2(mid+1,n,x);
    }
    return -1;
}

int main(){
    in >> n;
    for (int i=1; i<=n; i++)
        in >> a[i];
    in >> m;
    for (int i=1; i<=m; i++){
        in >> x >> y;
        if (x==0 || x==1) out << binarySearch1(1,n,y) << "\n";
        else out << binarySearch2(1,n,y) << "\n";
    }
    return 0;
}