#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

int main(){
    int n;
    fin >> n;
    long long v[n];
    for(int i=0;i<n;i++)
        fin >> v[i];
    int m;
    fin >> m;
    for(int i=0;i<m;i++){
        int cer,x;
        fin >> cer >> x;
        if(cer==0){
            int lf=0,rg=n-1;
            int poz=-1;
            while(lf<=rg){
                int mid=(lf+rg)/2;
                if(x==v[mid]){
                    poz=mid;
                    break;
                }
                if(x<v[mid])
                    rg=mid-1;
                else
                    lf=mid+1;
            }
            if(poz==-1)
                fout << poz << endl;
            else{
                int rasp=poz;
                bool gasit=false,spec=false;
                if(v[poz]==v[n-1]){
                    fout << n-1 << endl;
                    gasit=true;
                    spec=true;
                }
                for(int r=poz;gasit==false && r<n;r++){
                    if(v[poz]!=v[r])
                        gasit=true;
                    else
                        rasp++;
                }
                if(spec==false)
                    fout << rasp << endl;
            }
        }
        if(cer==1){
            int lf=0,rg=n-1;
            int poz=0;
            while(lf<=rg){
                int mid=(lf+rg)/2;
                if(v[mid]<=x){
                    poz=mid+1;
                    lf=mid+1;
                }
                else
                    rg=mid-1;
            }
            fout << poz << endl;
        }
        if(cer==2){
            int lf=0,rg=n-1;
            int poz=0;
            while(lf<=rg){
                int mid=(lf+rg)/2;
                if(v[mid]>=x){
                    poz=mid+1;
                    rg=mid-1;
                }
                else
                    lf=mid+1;
            }
            fout << poz << endl;
        }
    }
}