#include<fstream>
#define limit 100000
using namespace std;

int mat[limit];
int n,m;

int findbin(int value)
{
    int Left=0, Right=n-1, Mid;

    while (Left!=Right-1) {
        Mid=(Left+Right)/2;
        if (mat[Mid]==value) return Mid;
        else if (Left==Right-1 && mat[Left]<value && mat[Right]>value) return -1;
        else if (mat[Mid]<value) Left=Mid;
        else if (mat[Mid]>value) Right=Mid;
    }
    return -1;
}


int main()
{
    int quest, x, pos;
    ifstream in ("cautbin.in");
    ofstream out ("cautbin.out");
    in>>n;
    for (int i=0;i<n;i++)
        in>>mat[i];
    in>>m;
    for (int i=0;i<m;i++)
    {   in>>quest>>x;
        pos=findbin(x);
        if (quest==0) {
            if (pos==-1) out<<-1<<endl;
            else {
                while (mat[pos]==x && pos<n) pos++;
                out<<pos<<endl;
            }
        }
        else if (quest==1) {
            while (pos==-1) {
                x++; pos=findbin(x);
            }
            out<<pos<<endl;
        }
        else if (quest==2) {
            while (pos==-1 && x>=0) {
                x--; pos=findbin(x);
            }
            out<<pos+2<<endl;
        }
    }

    in.close();
    out.close();
    return 0;
}