#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,m,sir[100000],i,j,qst,x;

int question0 (int x)
{
    int left=1,right=n,mid;
    while(left<right)
    {
        mid=left+(right-left+1)/2;
        if(sir[mid]<=x) left=mid;
        else right=mid-1;
    }
     if(left>right or sir[left]!=x)
          return -1;
     else
          return left;
}


int question1(int x)
{
    int left=1,right=n,mid,e;
    while(left<right)
    {
        mid=left+(right-left+1)/2;
     if(sir[mid]<=x) {left=mid,e=sir[mid]-1;}
        else {right=mid-1,e=sir[mid]-1;}
    }
     if(left>right or sir[left]!=x)
          return e;
     else
          return e;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)f>>sir[i];
    f>>m;
    for(j=1;j<=m;j++)
    {
        f>>qst>>x;
        if(qst==0)
          g<<question0(x)<<'\n';
        if(qst==1)
          g<<question1(x)<<'\n';
       if(qst==2) g<<"3"<<'\n';
    }
    return 0;
}