#include<fstream>
using namespace std;
int n,ras,x,a[100002],m,st,dr,mid;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int main()
{
    fin>>n;
for(int i=1;i<=n;i++) fin>>a[i];

fin>>m;

while(m){

    m--;
    fin>>ras>>x;
    st=1;dr=n;
//0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir

    if(ras==0) {
        while(st<=dr){
        mid=int((st+dr)/2);
        if(a[mid]==x) break;
        else if(a[mid]>x) dr=mid-1;
        else  st=mid+1;
        }
    if(st<=dr) {while(a[mid+1]==x) mid++; fout<<mid<<'\n';}
    else fout<<"-1\n";
    }
//1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir.

    else if(ras==1) {while(st<=dr){
                mid=(st+dr)/2;
        if(a[mid]==x) break;
        else if(a[mid]>x) dr=mid-1;
        else st=mid+1;
        }
    if(st<=dr) {while(a[mid+1]==x) mid++; fout<<mid<<'\n';}
    else fout<<dr<<'\n';}

//2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir.

    else  {while(st<=dr){
                mid=(st+dr)/2;
        if(a[mid]==x) break;
        else if(a[mid]>x) dr=mid-1;
        else st=mid+1;
        }
    if(st<=dr) {while(a[mid-1]==a[mid])mid--; fout<<mid<<'\n';}
    else fout<<st<<'\n';
}}
    return 0;
}