//
//  main.cpp
//  BinarySearch
//
//  Created by Cristina Radulescu on 10/18/16.
//  Copyright © 2016 Cristina Radulescu. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int v[100000], N;

int binary_search(int left, int right, int x){
    if(left > right)
        return -1;
    
    int m = left + (right-left)/2;
    if(v[m] == x){
        while(m < N && v[m] == v[m+1])
            m++;
        return m;
    }
    else if(v[m] > x)
        return binary_search(left, m-1, x);
    else
        return binary_search(m+1, right, x);
}

int lowerBound_BS(int left, int right, int x){
    if(left > right)
        return -1;
    
    int m = left + (right-left)/2;
    if(v[m] <= x && x <= v[m+1]){
        while(m < N && v[m] <= x && x <= v[m+1])
            m++;
        return m-1;
    }
    else if(v[m] >= x)
        return lowerBound_BS(left, m-1, x);
    else
        return lowerBound_BS(m+1, right, x);
}

int upperBound_BS(int left, int right, int x){
    if(left > right)
        return -1;
    
    int m = left + (right-left)/2;
    if(v[m] <= x && x <= v[m+1]){
        while(m > 0 && v[m] <= x && x <= v[m+1])
            m--;
        return m+1;
    }
    else if(v[m] > x)
        return lowerBound_BS(left, m-1, x);
    else
        return lowerBound_BS(m+1, right, x);
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    freopen("cautarebinara.in", "r", stdin);
    freopen ("cautarebinara.out","w", stdout);
    
    int x, queries, type;
    
    cin >> N;
    for(int i = 1; i <= N; ++i){
        cin >> x;
        v[i] = x;
    }
    
    cin >> queries;
    for(int i = 0; i < queries; ++i){
        cin >> type >> x;
        if( type == 0)
            cout << binary_search(1, N, x) << endl;
        else if (type == 1)
            cout << lowerBound_BS(1, N, x) << endl;
        else if(type == 2)
            cout << upperBound_BS(1, N, x) << endl;
    }
    
    return 0;
}