#include <bits/stdc++.h>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

 unsigned long int n,a[100010],m,query,x;
int cautbin(int st,int dr,int q, int x)
{
    if(query==0)
    { if(st==dr)
        if (a[st]==x) return st;
        else return -1;
        int mid=(st+dr)/2;
        if(x==a[mid])
        {
            if(a[mid+1]!=x) return mid;
            else return cautbin(mid+1,dr,0,x);
        }else
        {
            if(x<a[mid]) return cautbin(st,mid-1,0,x);
            if(x>a[mid]) return cautbin(mid+1,dr,0,x);
        }
    } else if(query==1)
    {if(st==dr) return st;
        int mid=(st+dr)/2;
        if(x<=a[mid])
        {
            if(x==a[mid]) if(a[mid+1]>x) return mid; else return cautbin(mid+1,dr,1,x);
            else return cautbin(st,mid-1,1,x);
        }else
        {
            return cautbin(st,mid-1,1,x);
        }

    } else if(query==2)
    {
        if(st==dr) return st;
        int mid=(st+dr)/2;
        if(x>=a[mid]){
        if(x==a[mid]) if(a[mid-1]<x) return mid; else return cautbin(st,mid-1,2,x);
        if(x>a[mid]) return cautbin(mid+1,dr,2,x);
        }else return cautbin(mid+1,dr,2,x);
    }

}

int main()
{
    in>>n;
    for(int i=1;i<=n;i++)in>>a[i];
    in>>m;
    for(int i=1;i<=m;i++)
    {
        in>>query>>x;
        out<<cautbin(1,n,query,x)<<'\n';
    }
    return 0;
}