#include <iostream>
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

int n;
fin>>n;

int v[n];


int cautareBinara0(int stg, int dr, int val) {

    int mid;

    while (stg <= dr) {

        mid = stg + (dr-stg)/2;

        if (v[mid] <= val)

            stg = mid + 1;

        else

            dr = mid - 1;

    }

    mid = stg + (dr-stg)/2;

    if (v[mid] > val) mid --;

    if (v[mid] == val)

        return mid;

    return -1;

}


int cautareBinara1(int stg, int dr, int val) {

    int mid;

    while (stg < dr){

        mid = stg + (dr-stg)/2;

        if (v[mid] <= val)

            stg = mid + 1;

        else

            dr = mid;

    }

	mid = stg + (dr-stg)/2;

    if (v[mid] > val)

       mid--;

    return mid;

}


int cautareBinara2(int stg, int dr, int val) {

    int mid;


    while (stg < dr) {

        mid = stg + (dr-stg)/2;

        if (v[mid] < val)

            stg = mid + 1;

        else

            dr = mid;

    }

    mid = stg + (dr-stg)/2;

    if (v[mid] < val)

       mid++;

    return mid;
}



int main () {

    int m, tip, x;

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

    fin>>m;

    for(int i=1;i<=m;i++){
          fin>>tip;
          fin>>x;
          if (tip == 0)

             fout<<cautareBinara0(1,n,x)<<endl;

          if (tip == 1)

             fout<<cautareBinara1(1,n,x)<<endl;

          if (tip == 2)

             fout<<cautareBinara2(1,n,x)<<endl;

    }

    return 0;

}