#include <bits/stdc++.h>

using namespace std;

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

int const lim=100001;
int n,v[lim],k;

int cautbn1(int l , int r, int x)
{
    if(l>r) return -1;

    int mid=(l+r)/2;
    if(v[mid]==x && v[mid+1]==x)
        return cautbn1(mid+1,r,x);

    if(v[mid]==x)
        return mid;

    if(v[mid]>x)
        return cautbn1(l,mid-1,x);

    if(v[mid]<x)
        return cautbn1(mid+1,r,x);
}

int cautbn2(int l, int r, int x)
{
    if(l>r) return -1;

    int mid=(l+r)/2;

    if(v[mid]<=x && v[mid+1]>x)
        return mid;

    if(v[mid]>x)
        return cautbn2(l,mid-1,x);

    if(v[mid]<=x && v[mid+1]<=x)
        return cautbn2(mid+1,r,x);
}

int cautbn3(int l , int r, int x)
{
    if(l>r) return -1;

    int mid=(l+r)/2;

    if(v[mid]>=x && v[mid-1]<x)
        return mid;

    if(v[mid]<x)
        return cautbn3(mid+1,r,x);

    if(v[mid]>=x && v[mid-1]>=x)
        return cautbn3(l,mid-1,x);
}

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

    in>>k;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        in>>y>>x;
        if(y==0)
            out<<cautbn1(1,n,x)<<'\n';
        if(y==1)
            out<<cautbn2(1,n,x)<<'\n';
      if(y==2)
            out<<cautbn3(1,n,x)<<'\n';
    }
}