#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n,v[100005];
int cautbin0(int x)
{
    int prev=0,next=n-1,mid;
    while (prev<next)
    {
        mid=(prev+next)/2;
        if(v[mid]==x && v[mid+1]>x)
            return mid+1;
        if(v[mid]>x)
            next=mid;
        else
            prev=mid;
    }
    if(v[next]==x)
        return next+1;
    return -1;
}
int cautbin1(int x)
{
    int prev=0,next=n-1,mid;
    while (prev<next)
    {
        mid=(prev+next)/2;
        if(v[mid]<=x &&!(v[mid+1]<=x))
            return mid+1;
        if(v[mid]>x)
            next=mid;
        else
            prev=mid;
    }
    if(v[next]<=x &&!(v[next+1]<=x))
        return next+1;
    return -1;
}
int cautbin2(int x)
{
    int prev=0,next=n-1,mid;
    while (prev<next)
    {
        mid=(prev+next)/2;
        if(v[mid]>=x &&!(v[mid-1]>=x))
            return mid+1;
        if(v[mid]<x)
            prev=mid;
        else
            next=mid;
    }
    if(v[next]>=x &&!(v[next-1]>=x))
        return next+1;
    return -1;
}
int main()
{
    int a;
    cin >> n;
    for (int i=0; i<n; i++)
    {
        cin >> a;
        v[i]=a;
    }
    int m,p;
    cin >> m;
    for (int i=0; i<m; i++)
    {
        cin >> p>>a;
        if(p==0)
            cout << cautbin0(a)<<'\n';
        if(p==1)
            cout << cautbin1(a)<<'\n';
        if(p==2)
            cout << cautbin2(a)<<'\n';
    }
    return 0;
}