#include <iostream>
#include<fstream>
#include<cstring>
#include<algorithm>
#include<iomanip>
#define N 100005
using namespace std;

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

int n,a[100005];

int cautare1(int s,int d,int x)
{
    if(s>d)return -1;
    else
    {
        int m=(s+d)/2;
        if(a[m]==x&&(a[m+1]>x||m==n))return m;
        else if(x<a[m])return cautare1(s,m-1,x);
            else return cautare1(m+1,d,x);
    }
}

int cautare2(int s,int d,int x)
{
    if(s>d)return -1;
    else
    {
        int m=(s+d)/2;
        if(a[m]<=x&&(a[m+1]>x||m+1==n))return m;
        else if(x<a[m])return cautare2(s,m-1,x);
            else return cautare2(m+1,d,x);
    }
}

int cautare3(int s,int d,int x)
{
    if(s>d)return -1;
    else
    {
        int m=(s+d)/2;
        if(a[m]==x&&(a[m-1]<x||m==1))return m;
        else if(x>a[m])return cautare3(m+1,d,x);
            else return cautare3(s,m-1,x);
        cout<<1;
    }
}

void read()
{
    int i,m,task,x;
    fin>>n;
    for(i=1;i<=n;++i)fin>>a[i];
    fin>>m;
    for(i=1;i<=m;++i)
    {
        fin>>task>>x;
        if(task==0)fout<<cautare1(1,n,x)<<"\n";
        if(task==1)fout<<cautare2(1,n,x)<<"\n";
        if(task==2)fout<<cautare3(1,n,x)<<"\n";

    }
}




int main()
{
    read();


    return 0;
}