#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,x,y,m,v[100001],i,h;

int caut0(int s, int d)
{
if(s>d)
return -1;
else
{
m =(s+d)/2;
if (x==v[m] && v[m-1]<=x && v[m+1]>x)
return m;
if (x<v[m])
return caut0(s,m-1);
else return caut0(m+1,d);
}}
int caut1(int s,int d)
{if (s>d) return -1;
else
{
m=(s+d)/2;
if(v[m]<=x && v[m+1]>v[m])
    return m;
if(v[m]>x && v[m-1]<=x)
return caut1(s,m-1);
if (x<v[m])return caut0(s,m-1);
else return caut1(m+1,d);
}}
int caut2 (int s,int d)
{if(s>d)return -1;
else
{
    m=(s+d)/2;
if(v[m]>=x && v[m+1]>=v[m] && v[m-1]<x)return m;
if(v[m]>=x && v[m-1]==v[m])return caut2(s,m-1);
if (x<v[m])return caut0(s,m-1);
return caut2(m+1,d);
}}
int main()
{fin>>n;
for(i=1;i<=n;i++)fin>>v[i];
fin>>h;
for(i=1;i<=h;i++)
    {
    fin>>y>>x;
if(y==0)fout<<caut0(1,n);
else if(y==1)fout<<caut1(1,n);
else fout<<caut2(1,n);
fout<<"\n";    }

return 0;
}