#include <cstdio>

using namespace std;
int a[100010],n,i,j,op,x,m;

void cautare (int op, int x)
{
    int st,dr,m;
    st=1; dr=n;
    while (st<=dr)
    {
        m=(st+dr)/2;
        if (a[m]==x) break;
        else
           if (a[m]>x) dr=m-1; else st=m+1;
    }

    if (op==0)
        if (st>dr) printf("%d\n",-1);
           else
           {
              while (a[m]==x) m++;
              printf("%d\n",m-1);
           }
    if (op==1)
        if (st>dr) printf("%d\n",st-1);
          else
            {
                while (a[m]==x) m++;
                printf("%d\n",m-1);
            }
    if (op==2)
       if (st>dr) printf("%d\n",st);
       else
       {
           while (a[m]==x) m--;
           printf("%d\n",m+1);
       }

}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<=n; i++)
        scanf("%d ",&a[i]);
    scanf("%d\n",&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d %d",&op,&x);
        cautare(op,x);
    }
    return 0;
}