#include <iostream>

using namespace std;

int v[100001];

int cautare_binara_1(int st,int dr,int x)
{
    if(st > dr) {
        return -1;
    }
    int mij=(dr+st)/2;
    if(v[mij]==x) {
        // mij
        int ans = cautare_binara_1(mij + 1, dr, x);
        if(ans == -1)
            return mij;
        else
            return ans;
    }
    else
    {
        if(v[mij]>x)
            cautare_binara_1(st,mij-1,x);
        else
            cautare_binara_1(mij+1,dr,x);
    }
}

int cautare_binara_2(int st,int dr, int x)
{
    if(st>dr)
        return -1;
    else
    {
    int mij=(st+dr)/2;
    if(v[mij]>x)
        cautare_binara_2(st,mij-1,x);
    else
        {
        int ans=cautare_binara_2(mij+1,dr,x);
        if(ans==-1)
            return mij;
        else
            return ans;
        }
    }
}

int cautare_binara_3(int st,int dr, int x)
{
    if(st>dr)
        return -1;
    else
    {
    int mij=(st+dr)/2;
    if(v[mij]<x)
        cautare_binara_3(mij+1,dr,x);
    else
        {
        int ans=cautare_binara_3(st,mij-1,x);
        if(ans==-1)
            return mij;
        else
            return ans;
        }
    }
}


int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    int i,n,x,p,c,m;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>c>>p;
        if(c==0)
           x=cautare_binara_1(1,n,p);
        if(c==1)
            x=cautare_binara_2(1,n,p);
        if(c==2)
            x=cautare_binara_3(1,n,p);
        cout<<x<<"\n";
    }

    return 0;
}