#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
vector <int> v;

int cautbin (int q, int nr,int n)
{
int i=1, j=n;
switch (q)
{
    case 0:
        while (i<j)
            {if (v[(i+j)/2]>nr)
                j=(i+j)/2; else
                i=(i+j)/2;
            if (abs(i-j)==1)
            {
                if(v[j]==nr)
                    i=j; else
                    j=i;
            }
            }
        if (v[i]==nr)
        return i;
        return -1;
        break;
    case 1:
        while (i<j)
            {if (v[(i+j)/2]>nr)
                j=(i+j)/2; else
                i=(i+j)/2;
            if (abs(i-j)==1)
            {if(v[j]<=nr)
                    i=j; else
                    j=i;
            }
            }
        return i;
        break;
    default:
         while (i<j)
            {if (v[(i+j)/2]>=nr)
                j=(i+j)/2; else
                i=(i+j)/2;
            if (abs(i-j)==1)
            {    if(v[i]>=nr)
                    j=i; else
                    i=j;
            }
            }
        return i;
        break;
}
}

int main()
{
    ifstream f ("cautbin.in");
    ofstream g ("cautbin.out");
    int n, m;
    f>>n;
    v.push_back(-1);
    for (int i = 1; i <= n; i++)
        {
            int p;
            f>>p;
            v.push_back(p);
        }
    f>>m;
    int q, nr;
    for (int i = 1; i<=m; i++)
    {
        f>>q>>nr;
        g<<cautbin(q, nr,n)<<"\n";
    }
    return 0;
}