//
//  main.cpp
//  CautareBinara
//
//  Created by Anca Tache on 03/12/2017.
//  Copyright © 2017 Anca Tache. All rights reserved.
//

#include <iostream>
#include <fstream>


int functia1(int v[],int y, int f, int l)
{
    int mij;
    if(f==l) return -1;
    else
    {
        mij=f +(l-f)/2;
        if(y==v[mij])
        {
            if(v[mij+1]!=v[mij])
                return mij;
            else
                return functia1(v,y,mij+1,l);
        }
        else if(y<v[mij])
            return functia1(v,y,f,mij-1);
        else
            return functia1(v,y,mij+1,l);
    }
}

int functia2(int v[],int y,int f, int l)
{
    int mij;
    mij=f +(l-f)/2;
    if(v[mij]==y)
    {
        if(v[mij+1]!=v[mij])
            return mij;
        else
            return functia2(v,y,mij,l);
    }
    else if(v[mij]<y)
    {
        if(v[mij+1]>y)
            return mij;
        else
            return functia2(v,y,mij,l);
    }
    return 0;
}

int functia3(int v[],int y, int f, int l, int n)
{
    int mij;
    mij=f +(l-f)/2;
    if(v[mij]==y)
    {
        if(v[mij-1]!=v[mij])
            return mij;
        else
            return functia3(v,y,f,mij,n);
    }
    else if(v[mij]>y)
    {
        if(v[mij-1]<y)
            return mij;
        else
            return functia3(v,y,f,mij,n);
    }
    return n;

}

int main(int argc, const char * argv[]) {
    
    std::ifstream f;
    std::ofstream g;
    int n,nr,x,y;
    f.open("cautbin.in");
    g.open("cautbin.out");
    f>>n;
    int *v =new int[n];
    for(int i=1;i<=n;i++)
        f>>v[i];
    f>>nr;
    for(int i=0;i<nr;i++)
    {
        f>>x>>y;
        if(x==0)
            g<<functia1(v,y,1,n)<<"\n";
        else if(x==1)
            g<<functia2(v,y,1,n)<<"\n";
        else if(x==2)
            g<<functia3(v,y,1,n,n)<<"\n";
    }
    f.close();
    g.close();
    
    return 0;
}