#include <iostream>

#include <fstream>

#include <algorithm>

using namespace std;

ifstream in("cautbin.in");

ofstream out("cautbin.out");

int N, v[100001], M , intrebare, z;



int bin0x(int x, int y){

    int lo = 1, hi = y, mid, fin = hi;

    while(lo <= hi){

        mid = lo + (hi - lo) / 2;

        if(v[mid] < x){

            lo = mid + 1;

        }else if(v[mid] == x){

            fin = mid;

            lo = mid + 1 ;

            hi = y;

        }else{

            hi = mid - 1;

            fin = hi;

        }

    }

    if(v[fin] == x){

        return fin;

    }else {

        return -1;

    }

}



int bin1x(int x, int y){

    int lo = 1, hi = y, mid, fin = hi;

    while(lo <= hi){

        mid = lo + (hi - lo) / 2;

        if(v[mid] > x){

            hi = mid - 1;

        }else if(v[mid] <= x){

            fin = mid;

            lo = mid + 1;

        }

    }

    return fin;

}



int bin2x(int x, int y){

    int lo = 1, hi = y, mid,fin = hi;

    while(lo <= hi){

        mid = lo + (hi - lo) / 2;

        if(v[mid] < x){

            lo = mid + 1;

        }else if(v[mid] >= x){

            fin = mid;

            hi = mid - 1;

        }

    }

    return fin;

}



int main() {

    in>>N;

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

      in>>v[i];

    }

    in>>M;

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

        in>>intrebare>>z;

        if(intrebare == 0){

            out<<bin0x(z, N)<<'\n';

        }else if(intrebare == 1){

            out<<bin1x(z, N)<<'\n';

        }else{

            out<<bin2x(z, N)<<'\n';

        }

    }

}