#include <bits/stdc++.h>
#define DIM 100001

using namespace std;

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

int v[DIM];

int n, Q, i, task, x;

int solve1(int target){
    int st = 1, dr = n, sol = 0;
    while(st <= dr){
        int mij = (st + dr) >> 1;
        if(v[mij] <= target){
            sol = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    if(v[sol] == target)
        return sol;
    return -1;
}

int solve2(int target){
    int st = 1, dr = n, sol = 0;
    while(st <= dr){
        int mij = (st + dr) >> 1;
        if(v[mij] <= target){
            sol = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return sol;
}

int solve3(int target){
    int st = 1, dr = n, sol = 0;
    while(st <= dr){
        int mij = (st + dr) >> 1;
        if(v[mij] >= target){
            sol = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    return sol;
}

int solve(int task, int target){
    switch(task){
        case 0:
            return solve1(target);
            break;
        case 1:
            return solve2(target);
            break;
        case 2:
            return solve3(target);
            break;
        default:
            assert(0);
    }
}

int main(){

    ios :: sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);

    fin >> n;

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

    fin >> Q;

    while(Q--){
        fin >> task >> x;
        fout << solve(task, x) << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}