#include <iostream>
#include <fstream>
using namespace std;

ifstream in("D:\\binary_search\\cautbin.in");
ofstream out("D:\\binary_search\\cautbin.out");

const int Max=100005;

int v[Max]; int n,m;

void solve(){
    in>>n;

    for(int i=1;i<=n;i++)
        in>>v[i];

    in>>m;

    for(int i=1;i<=m;i++){

        int x,y;
        in>>x>>y;

        int st=1,dr=n;

        int poz=-1;

        if(x==0){

            while(st<=dr){

                int mid=(st+dr)/2;

                if(v[mid]==y){
                    poz=mid;
                    st=mid+1;
                }

                else if(v[mid]<y){
                    st=mid+1;
                }

                else{
                    dr=mid-1;
                }



            }

        }

        else if(x==1) {

            while (st <= dr) {

                int mid = (st + dr) / 2;

                if (v[mid] <= y) {
                    poz = mid;
                    st = mid + 1;
                }

                else{
                    dr = mid - 1;
                }

            }

        }

        else{

            while (st <= dr) {

                int mid = (st + dr) / 2;

                if (v[mid] < y) {
                    st = mid + 1;
                }

                else{
                    poz=mid;
                    dr = mid - 1;
                }



            }

        }

        out<<poz<<"\n";


    }
}

int main() {

    solve();

    return 0;
}