#include <cstdio>

using namespace std;
int i, q, x, n, m, p, u, k, v[100005];
int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &n);
    for(i=1;i<=n;i++)
        scanf("%d", &v[i]);
    scanf("%d", &m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &q, &x);
        if(q==0)
        {
            if(x<v[1]||x>v[n]) printf("-1\n");
            else if(x==v[n]) printf("%d\n", n);
            else
            {
                p=1;
                u=n;
                while(p<=u)
                {
                    k=(p+u)/2;
                    if(v[k]==x&&v[k+1]>x)
                    {
                        printf("%d\n", k);
                        break;
                    }
                    else if(v[k]<=x) p=k+1;
                    else u=k-1;
                }
                if(p>u) printf("-1\n");
            }
        }
        else if(q==1)
        {
            if(x>=v[n]) printf("%d\n", n);
            else if(x<v[1]) printf("1\n");
            else
            {
                p=1;
                u=n;
                while(p<=u)
                {
                    k=(p+u)/2;
                    if(v[k]<=x&&v[k+1]>x)
                    {
                        printf("%d\n", k);
                        break;
                    }
                    else if(v[k]<=x) p=k+1;
                    else u=k-1;
                }
            }
        }
        else
        {
            if(x<v[1]) printf("1\n");
            else if(x>v[n]) printf("%d\n", n);
            else
            {
                p=1;
                u=n;
                while(p<=u)
                {
                    k=(p+u)/2;
                    if(x<=v[k]&&v[k-1]<x)
                    {
                        printf("%d\n", k);
                        break;
                    }
                    else if(x<=v[k]) u=k-1;
                    else p=k+1;
                }
            }
        }
    }
    return 0;
}