#include <bits/stdc++.h>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

struct intrb
{
    int nr;
    int val;

};


int cautbin(const vector<int> &v, int x)
{
    int a = 0;
    int b = v.size() - 1;

    while(a <= b)
    {
        int mij = a + (b - a) / 2;
        if(x < v[mij])
        {
            b = mij - 1;
        }
        else if(x > v[mij])
        {
            a = mij + 1;
        }
        else
        {
            return mij;
        }
    }

    return -1;
}

intrb s[100001];

int main()
{

    vector<int>v;
    int n;
    fin>>n;

    for(int i=1; i<=n; i++)
    {
        int a;
        fin>>a;
        v.push_back(a);

    }

    int m;
    fin>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>s[i].nr>>s[i].val;

        if(s[i].nr==0)
        {
            int a=cautbin(v,s[i].val);
            if(a!=-1)
            {
                while(v[a]==s[i].val && a<n)
                {
                    a++;
                }
            }

            fout<<a<<'\n';

        }

        else if(s[i].nr==1)
        {
            int a=cautbin(v,s[i].val);
            if(a!=-1)
            {
                while(v[a]==s[i].val)
                {
                    a++;
                }
                fout<<a<<'\n';
            }
            else
            {

                while(cautbin(v,s[i].val)==-1)
                {
                    s[i].val--;


                }

                fout<<cautbin(v,s[i].val)<<'\n';

            }


        }

        else
        {
            int a = cautbin(v, s[i].val);
            if(a != -1)
            {
                while(a > 0 && v[a-1] == s[i].val)
                    a--;
                fout << a+1<< '\n';
            }


            else
            {
                while(cautbin(v,s[i].val)==-1)
                {
                    s[i].val++;

                }

                fout<<cautbin(v,s[i].val)<<'\n';

            }



        }





    }
}