#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

void cautbin(int prob, int x, int v[100002],int n)
{
    int st = 1, dr=n;v[n+1] = INT_MAX;
    switch(prob)
    {
    case 0:
        {

                while(st <= dr)
                {
                    int mid = (dr+st)/2;
                    if(v[mid] == x && v[mid+1]>x)
                    {
                         g<<mid<<endl;
                         return;
                    }
                    if(v[mid]>x)
                    {
                        dr = mid-1;
                    }
                    else
                    {
                       st = mid +1;
                    }
                }g<<-1<<endl;
            }
            break;
    case 1:
        {

                while(st <= dr)
                {
                    int mid = (dr+st)/2;
                    if(v[mid] <= x && v[mid+1]>x)
                    {
                         g<<mid<<endl;
                         return;
                    }
                    if(v[mid]>x)
                    {
                        dr = mid-1;
                    }
                    else
                    {
                       st = mid +1;
                    }
                }g<<-1<<endl;

            break;
        }
    case 2:
        {
                v[0] = INT_MIN;
                while(st <= dr)
                {
                    int mid = (dr+st)/2;
                    if(v[mid] >= x && v[mid-1]<x)
                    {
                         g<<mid<<endl;
                         return;
                    }
                    if(v[mid]>=x)
                    {
                        dr = mid-1;
                    }
                    else
                    {
                       st = mid +1;
                    }
                }g<<-1<<endl;

            break;
        }
        default:
            break;
    }
}

int main()
{
    int v[100002],n,nrp;
    f>>n;
    for(int i=1 ; i<=n; i++ )
        f>>v[i];
    f>>nrp;
    int p,x;
    for(int i=1;i<=nrp;i++)
    {
         f>>p>>x;
         cautbin(p,x,v,n);
    }


    return 0;
}