#include <fstream>

using namespace std;

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

int n,i,j,nr,v[100001],m,lo,hi,mid,a,p;
bool ok;

int main()
{
    fin >> n;

    for(i = 1; i <= n; ++i)
        fin >> v[i];

    fin >> m;

    for(i = 1; i <= m; ++i)
        {
            fin >> p >> a;

            if(!p)
                {
                  lo = 1;
                    hi = n;
                    while(lo<hi)
                        {
                            mid = lo + (hi-lo)/2;
                            if(v[mid]<a)
                                lo = mid+1;
                            else if(v[mid]>a)
                                hi = mid - 1;
                                else {if((v[mid+1]>a)&&(v[mid]==a))
                                        {
                                            ok = 1;break;}
                                    lo = mid;}
                        }
                    if(ok)fout << mid << '\n';
                    else fout << "-1" << '\n';
                    ok = 0;
                }
            else if(p==1)
                {
                  lo = 1;
                    hi = n;
                    while(lo<hi)
                        {
                            mid = lo + (hi-lo)/2;
                            if(v[mid]>a)
                                lo = mid+1;
                            else if(v[mid]<a)
                                hi = mid-1;
                                else {if((v[mid]<=a)&&(v[mid+1]>a))
                                        break;
                                      lo = mid + 1;
                                }
                        }
                    if(v[mid]>a)
                        --mid;
                    fout << mid << '\n';
                }
            else{
                  lo = 1;
                    hi = n;
                    while(lo<hi)
                        {
                            mid = lo + (hi-lo)/2;
                            if(v[mid]<a)
                                lo = mid + 1;
                            else if(v[mid]>a)
                                hi = mid - 1;
                                else {if((v[mid]>=a)&&(v[mid-1]<a))
                                        break;
                                    hi = mid - 1;}
                        }
                    if(v[mid]<a)
                        ++mid;
                    fout << mid << '\n';
                }
        }


    return 0;
}