#include<fstream>
using namespace std;

int n,a[100005],b[100005][3],m;

int main()
{
    int i,st,dr,mij;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for (i=1;i<=m;i++)
        fin>>b[1][i]>>b[2][i];
    fin.close();
    for (i=1;i<=m;i++)
        {if (b[1][i]==0)
            {st=1;dr=n;
             mij=(st+dr)/2;
             while (st<dr && a[mij]!=b[2][i])
                {if (a[mij]<b[2][i] && mij<n)
                    st=mij+1;
                 if (mij>b[2][i] && mij>1)
                    dr=mij-1;
                 mij=(st+dr)/2;
                }
             while (st<dr && a[mij+1]==b[2][i])
                {if (a[mij]>b[2][i])
                    dr=mij-1;
                 else st=mij+1;
                 mij=(st+dr)/2;
                }
             if (st<dr)
             fout<<mij<<"\n";
             else fout<<"-1"<<"\n";
            }
         if (b[1][i]==1)
            {st=1;dr=n;
             mij=(st+dr)/2;
             while (st<dr && a[mij]!=b[2][i])
                {if (a[mij]<b[2][i] && mij<n)
                    st=mij+1;
                 if (mij>b[2][i] && mij>1)
                    dr=mij-1;
                 mij=(st+dr)/2;
                }
             while (st<dr && a[mij+1]==b[2][i])
                {if (a[mij]>b[2][i])
                    dr=mij-1;
                 else st=mij+1;
                 mij=(st+dr)/2;
                }
              if (st<dr)
             fout<<mij<<"\n";
             else if (a[mij]>b[2][i]) fout<<mij-1<<"\n";
             else fout<<mij<<"\n";
            }
         if (b[1][i]==2)
            {st=1;dr=n;
             mij=(st+dr)/2;
             while (st<dr && a[mij]!=b[2][i])
                {if (a[mij]<b[2][i] && mij<n)
                    st=mij+1;
                 if (mij>b[2][i] && mij>1)
                    dr=mij-1;
                 mij=(st+dr)/2;
                }
             while (st<dr && a[mij-1]==b[2][i])
                {if (a[mij]>b[2][i])
                    st=mij+1;
                 else dr=mij-1;
                 mij=(st+dr)/2;
                }
             if (a[mij]<b[2][i]) fout<<mij+1<<"\n";
             else fout<<mij<<"\n";
            }
        }
    fout.close();
    return 0;
}