#include <bits/stdc++.h>
using namespace std;

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

vector <int> v;

int main()
{
    int n, m, a, b, x;
    fin>>n;
    while(n)
    {
        fin>>m;
        v.push_back(m);
        n--;
    }
    fin>>m;
    while(m)
    {
        int st=0, dr=v.size()-1, mij, ok=0;
        fin>>a>>b;
        while(dr - st > 1 && !ok)
        {
            mij=(st+dr)/2;
            if(v[mij] == b)
             ok=1;
            else
             if(b > v[mij])
                 st=mij;
             else
                 dr=mij;
        }
        if(a == 0)
        {
            if(ok == 1)
             {
                 while(v[mij+1] == b)
                    mij++;
                 fout<<mij+1;
             }
            else
              fout<<-1;
        }
        else
        if(a==1)
        {
            if(v[mij] > b)
            {
                while(v[mij] > b)
                    mij--;
                fout<<mij;
            }
            else
            {
                while(v[mij+1] <= b)
                  mij++;
                fout<<mij+1;
            }
        }
        else
        if(a==2)
        {
            if(v[mij] < b)
            {
                while(v[mij]< b)
                    mij++;
                fout<<mij;
            }
            else
            {
                while(v[mij-1] >= b)
                    mij--;
                fout<<mij-1;
            }
        }
        fout<<"\n";
        m--;
    }
    return 0;
}