#include <bits/stdc++.h>
using namespace std;

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

int x[100001];
int n;

int srch(int y){
    int l = 0,r = n-1,res = -2;
    
    while(l <= r){
        int mid = l + (r - l) / 2;
        
        if(x[mid] <= y){
            l = mid+1;
            res = mid;
        } else {
            r = mid-1;
        }
    }
    
    if(res == -2 || x[res] != y)return -2;
    return res;
}

int srch1(int y){
    int l = 0,r = n-1,res = n-1;
    
    while(l <= r){
        int mid = l + (r - l) / 2;
        
        
        if(x[mid] <= y){
            l = mid+1;
            res = mid;
        } else {
            r = mid-1;
        }
    }
    
    return res;
}

int srch2(int y){
    int l = 0,r = n-1,res = 0;
    
    while(l <= r){
        int mid = l + (r - l) / 2;
        
        if(x[mid] < y){
            l = mid+1;
        } else {
            r = mid-1;
            res = mid;
        }
    }
    
    return res;
}

int res(int c, int nr){
    if(c == 0)return srch(nr);
    if(c == 1)return srch1(nr);
    return srch2(nr);
}

int main()
{
    fin >> n;
    
    for(int i = 0; i < n;i++){
        fin >> x[i];
    }
    
    int q,t,y;
    fin >> q;
    
    for(int i = 0;i < q;i++){
        fin >> t >> y;
        
        fout << res(t,y)+1 << endl;
    }
    

    return 0;
}