#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;
    if (mat[Left]==value) return Left;
    else if (mat[Right]==value) return Right;

    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) {
            if (pos!=-1) out<<pos+1<<endl;
            else if (x>=mat[n-1]) out<<n<<endl;
            else {
                while (pos==-1) {
                    x++; pos=findbin(x);
                }
                out<<pos<<endl;
            }

        }
        else if (quest==2) {
            if (pos!=-1) out<<pos+1<<endl;
            else if (x<=mat[0]) out<<1<<endl;
            else {
                while (pos==-1) {
                    x--; pos=findbin(x);
                }
                out<<pos+2<<endl;
            }
        }
    }

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