#include <cstdio>
using namespace std;
int n,m,i,v,st,dr,mij,poz,max1;
long long int x,min1,a[100002];
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %lld",&v,&x);
        st=1;
        dr=n;
        if(!v)
        {
            poz=0;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(a[mij]==x)
                {
                    poz=mij;
                    break;
                }
                else
                    if(a[mij]<x)
                        st=mij+1;
                    else
                        dr=mij-1;
            }
            if(!poz)
                printf("-1");
            else
            {
                while(a[poz]==x)
                    poz++;
                poz--;
                printf("%d",poz);
            }
        }
        else
            if(v==1)
            {
                max1=0;
                while(st<=dr)
                {
                    mij=(st+dr)/2;
                    if(a[mij]<=x)
                        if(a[mij]>max1)
                        {
                            poz=mij;
                            max1=a[mij];
                        }
                    else
                        dr=mij-1;
                }
                while(a[poz]==max1)
                    poz++;
                poz--;
                printf("%d",poz);
            }
            else
            {
                min1=9223372036854775807;
                while(st<=dr)
                {
                    mij=(st+dr)/2;
                    if(a[mij]>=x)
                        if(a[mij]<min1)
                        {
                            min1=a[mij];
                            poz=mij;
                        }
                    else
                        st=mij+1;
                }
                while(a[poz]==min1)
                    poz--;
                poz++;
                printf("%d",poz);
            }
        printf("\n");
    }
    return 0;
}