#include <bits/stdc++.h>
using namespace std;
# define ios ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef long long int lli;
typedef pair < int, int> dbl;
const int maxInt = 1e9*2;
const lli maxLong = 1e18*2;
vector <int> arr;

int BS0(int left, int right, int x){
        if(left > right)
                return(-1);
        int mid = left + (right - left) / 2;
        if(arr[ mid ]  >  x)
            return(BS0(left, mid - 1, x));
        if(arr[ mid ]  <  x)
            return(BS0(mid + 1, right, x));
        while(arr[mid] == x)
            mid++;
        return(mid);
}
int min0 = 0;
int BS1(int left, int right, int x){
       if(right - left == 1)
                return(left);
        int mid = left + (right - left) / 2;
        if(arr[ mid ]  >  x)
            return(BS1(left, mid - 1, x));
        if(arr[ mid ]  <  x){
            min0 = mid;
            return(BS1(mid + 1, right, x));
        }
        while(arr[mid] == x)
            mid++;
        return(mid);
}

int max0 = 0;
int BS2(int left, int right, int x){
       if(right - left == 1)
                return(right + 1);
        int mid = (right + left) / 2;
        if(arr[ mid ]  >  x)
            return(BS2(left, mid - 1, x));
        if(arr[ mid ]  <  x)
            return(BS2(mid + 1, right, x));
        else if(arr[mid] == x){
                while(arr[mid] == x)
                    mid--;
                mid+=2;
            return(mid);
        }
}

int main(){
           ifstream cin("cautbin.in");
           ofstream cout("cautbin.out");
           int n;
           cin >> n;
           for(int i = 0; i < n; ++i){
                int x ;
                cin >> x;
                arr.push_back(x);
                //cin >> arr[i];
           }
           int q;
           cin >> q;
           for(int i =0; i < q; ++i){
                    int type, nbr;
                    cin >> type >> nbr;
                    if(type == 0)
                            cout << BS0(0, n - 1, nbr) << endl;
                    if(type == 1)
                            cout << BS1(0, n - 1, nbr) << endl;
                    if(type == 2)
                            cout << BS2(0 , n - 1, nbr) << endl;
           }

           return(0);
}