#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){
        int mid;
        while(left <= right){
                mid = left + (right - left) / 2;
                if(arr[mid] > x)
                        right = mid - 1;
                else if(arr[mid] < x)
                        left = mid + 1;
                else {
                        while(arr[mid + 1] == x)
                                mid++;
                        return(mid);
                }
        }
        return(-1);
}

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

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

int main(){
          // ifstream cin("input.in");
           ifstream cin("cautbin.in");
           ofstream cout("cautbin.out");
           int n;
           cin >> n;
           arr.push_back(0);
           for(int i = 1; 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(1, n, nbr) << endl;
                    if(type == 1)
                            cout << BS1(1, n, nbr) << endl;
                    if(type == 2)
                            cout << BS2(1 , n, nbr) << endl;
           }

           return(0);
}