#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+2;
int n,m,a[NMAX],c,x;

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

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> a[i];
    }
    fin >> m;
    while(m--){
        fin >> c >> x;
        int st = 1, dr = n;
        int pos = 0;
        if(c == 0 || c == 1){
            while(st <= dr){
                int mid = ((st+dr)>>1);
                if(a[mid] <= x){
                    pos = mid;
                    st = mid+1;
                }else{
                    dr = mid-1;
                }
            }
            fout << ( (c == 1)? pos : ( (a[pos] == x)? pos : -1 )) << "\n";
        }else{
            while(st <= dr){
                int mid = ((st+dr)>>1);
                if(a[mid] >= x){
                    pos = mid;
                    dr = mid-1;
                }else{
                    st = mid+1;
                }
            }
            fout << pos << "\n";
        }
    }
    return 0;
}