#include <bits/stdc++.h>
#define optim ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define let auto
#define popcount __builtin_popcount
#define ctzll __builtin_ctzll
#define clzll __builtin_clzll

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





const int sze = 1e5;
unsigned int v[sze + 5];
int n;
int CB0(int st, int dr, int x){
    while(st <= dr){
        int mij = (st + dr)/2;
        if(v[mij] == x) {
            while(v[mij] == v[mij + 1]){
                ++mij;
            }
            return mij;
        }
        if(x < v[mij]){
            dr = mij - 1;
        }
        else{
            st = mij + 1;
        }
    }
    return -1;
}


int CB1(int st, int dr, int x){
    if(v[n] < x) return n;
    while(st <= dr){
        int mij = (st + dr)/2;
        if(v[mij] == x) {
            while(v[mij] == v[mij + 1] && mij != n){
                ++mij;
            }
            return mij;
        }
        if(x < v[mij]){
            dr = mij - 1;
        }
        else{
            st = mij + 1;
        }
    }
    if(x > v[st]){
        return st;
    }
    else{
        return st - 1;
    }
}
int CB2(int st, int dr, int x){
    while(st <= dr){
        int mij = (st + dr)/2;
        if(v[mij] == x) {
            while(v[mij] == v[mij - 1] && mij != 1){
                --mij;
            }
            return mij;
        }
        if(x < v[mij]){
            dr = mij - 1;
        }
        else{
            st = mij + 1;
        }
    }
    if(x < v[st]){
        return st;
    }
    else{
        return st + 1;
    }
}




int main()
{
    fin>>n;
    for(int i = 1;i<=n;++i){
        fin>>v[i];
    }
    int m;
    fin>>m;
    int op, a;
    while(m--){
        fin>>op>>a;
        switch (op){
            case 0:
            fout<<CB0(1, n, a)<<'\n';
            break;
            case 1:
            fout<<CB1(1, n, a)<<'\n';
            break;
            case 2:
            fout<<CB2(1,n,a)<<'\n';
            break;
        }
    }


    return 0;
}