#include <fstream>

using namespace std;

         int a[100000],b[20000];
int main()
{
    int i,n,m,st,dr,mij,j,r,ok,q;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
        fin >> n;
    for(i = 1;i<=n;i++) fin >> a[i];
    fin >> m; m*=2;
        for(i = 1;i<=m;i++) fin >> b[i];
        //fout << m*2<<" ";
    for (i = 2;i<=m;i+=2)
    {
        if (b[i-1] == 0)
            {
            st = 1; dr = n; j = -1;
                while(st < dr && j == -1)
                {
                    mij = (st+dr)/2;

                        if (a[mij] < b[i]) st = mij+1;
                        else if (a[mij] > b[i]) dr = mij-1;
                        else if (a[mij] == b[i]) j = mij;
                }

            if (j != -1)
                    { ok = 1;
                for(r = n;r>j&&ok == 1;r--)
                if (a[r] == b[i]) { ok = 1; j = r;}
                    }

               fout << j<<"\n";
            }
      else if (b[i-1] == 1)
            {       ok = 1;
            for(j = n;j>0 && ok == 1;j--)
            if (a[j] <= b[i]){ok = 0; q = j;}
                fout << q<<"\n";
            }
        else if (b[i-1] == 2)
        {
               ok = 1;
            for(j = 1;j<=n && ok == 1;j++)
            if (a[j] >= b[i]){ok = 0; q = j;}
                fout << q<<"\n";
        }
    }


   fin.close();
   fout.close();
    return 0;
}