#include <bits/stdc++.h>

    using namespace std;

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

    #define nmax 100005

    int bin[nmax];
    int n, tasklist;

    int task1(int x){
        int pos = -1;

        int lefty = 1, righty = n;

        while(lefty <= righty ){
            int mid = lefty + (righty - lefty) / 2;

            if(bin[mid] == x){
                pos = mid;
                lefty = mid + 1;
            }

           else if(bin[mid] < x){
                lefty = mid + 1;
            }
            else{
                righty = mid - 1;
            }
        }

        return pos;
    }

    int task2(int x){
        int pos = -1;

        int lefty = 1, righty = n;

        while(lefty <= righty){
            int mid = lefty + (righty - lefty) / 2;

            if(bin[mid] <= x){
                lefty = mid + 1;
                pos = mid;
            }
            else {
                righty = mid - 1;
            }
        }
        return pos;
    }

    int task3(int x){
        int pos = -1;

        int lefty = 1, righty = n;

        while(lefty <= righty ){
            int mid = lefty + (righty - lefty) / 2;

            if(bin[mid] >= x){
                pos = mid;
                righty = mid - 1;
            }
            else{
                lefty = mid + 1;
            }

        }

        return pos;

    }

    int main()
    {
        fin >> n;
        for(int i = 1; i <= n; i++){
            fin >> bin[i];
        }

        fin >> tasklist;

        while(tasklist--){
            int tasknum, x;
            fin >> tasknum >> x;

            if(tasknum == 0)
                fout << task1(x) << '\n';
            else if(tasknum == 1)
                fout << task2(x) << '\n';
            else if(tasknum == 2)
                fout << task3(x) << '\n';
        }

        return 0;
    }