#include <iostream>

#include <fstream>



using namespace std;



int a[100001];



void cautbin(int s, int d, int x, int &r) {

    int m;

    if(s<=d) {

        m = (s + d) / 2;

        if(a[m] < x) {

            cautbin(m+1, d, x, r);

        } else if(a[m] > x)

            cautbin(s, m-1, x, r);

        else {

            r = m;

            cautbin(m+1, d, x, r);

        }

    }

}



void cautbin1(int s, int d, int x,int &r) {

    int m;

    if(s <= d) {

     m = (s + d) / 2;

     if(a[m] <= x) {

            r = m;

        cautbin1(m+1, d, x, r);

     } else if(a[m] > x)

        cautbin1(s, m-1, x, r);

    }

}



void cautbin2(int s, int d, int x, int &r) {

    int m;

    if(s <= d) {

     m = (s + d) / 2;

     if(a[m] >= x) {

            r = m;

        cautbin2(s, m-1, x, r);

     } else if(a[m] < x)

        cautbin2(m+1, d, x, r);

    }

}



int main()

{

    ifstream cin("cautbin.in");

    ofstream cout("cautbin.out");

    int m, n, i, j, c, x;

    cin>>m;



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

        cin>>a[i];

    }



    cin>>n;

    int temp = 0;

    for(i = 1; i <= n; i++) {

        cin>>c>>x;

        if(c == 0) {

            temp = -1;

            cautbin(1, m, x, temp);

            cout<<temp;

        } else if(c == 1) {

            temp = 0;

            cautbin1(1, m, x, temp);

            cout<<temp;

        } else if(c == 2) {

            temp = 0;

            cautbin2(1, m, x, temp);

            cout<<temp;

        }

        cout<<'\n';

    }





    return 0;

}