#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int n, v[100001];

int bin_search0(int left, int right, int x)
{
    int mid=(left+right)/2;
    if (left==right)
        {
            if(v[left]==x)
             return mid;
        else
            return -1;
        }
    else
        {if (x>=v[mid+1])
           return bin_search0(mid+1,right,x);
        if (x>v[mid])
               return -1;
        if (x==v[mid])
            return  mid;
        if (mid-1>=left)
            return bin_search0(left, mid-1,x);
        return -1;
}
}

int bin_search1(int left, int right, int x)
{
    int mid= (left+right)/2;
    if (left==right)
        return mid;
    if (x>=v[mid+1])
        return bin_search1(mid+1,right,x);
    if (x>=v[mid])
    return mid;
    if (x<=v[mid-1])
        return bin_search1(left,mid-1,x);
}

int bin_search2(int left, int right, int x)
{
    int mid=(left+right)/2;
    if (x<=v[mid-1])
        return bin_search2(left,mid-1,x);
    if (x<=v[mid])
        return mid;
    return bin_search2(mid+1,right,x);

}

int main()
{
    int m,i,c,x;
    f>>n;
    for (i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>c>>x;
        if (c==0)
            g<<bin_search0(1,n,x)<<'\n';
        else
            if(c==1)
            g<<bin_search1(1,n,x)<<'\n';
               else
                  if(c==2)
                     g<<bin_search2(1,n,x)<<'\n';
    }
    f.close();
    g.close();
    return 0;

}