#include <bits/stdc++.h>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

vector<int> v;
int n;
int max_pos(int x)
{
    int st=0, dr=n-1;
    if(v[dr]==x)
        return dr+1;
    while(st!=dr)
    {
        int m=st+(dr-st)/2;
        if(v[m]==x && m+1<n && v[m+1]!=x)
            return m+1;
        if(v[m]>x)
            dr=m;
        else
            st=m+1;
    }
    return -1;
}
int less_than_x_max_pos(int x)
{
    int st=0, dr=n-1;
    int m;
    if(v[dr]==x)
        return dr+1;
    while(st!=dr)
    {
        m=st+(dr-st)/2;
        if(v[m]==x && m+1<n && v[m+1]!=x)
            return m+1;
        if(v[m]>x)
            dr=m;
        else
            st=m+1;
    }
    if(v[st]<=x)
        if(st+1<n && v[st+1]<=x)
            return st+2;
        else
            return st+1;
    else
        return st;
}

int greater_than_x_min_pos(int x)
{
    int st=0, dr=n-1;
    int m;
    if(v[st]==x)
        return st+1;
    while(st!=dr)
    {
        m=st+(dr-st)/2;
        if(v[m]==x && m+1<n && v[m-1]!=x)
            return m+1;
        if(v[m]>=x)
            dr=m;
        else
            st=m+1;
    }
    cout<<"mit";
    if(v[st]>=x)
        if(st>0 && v[st-1]>=x)
            return st;
        else
            return st+1;
    else
        return st+2;
}

void rd()
{
    f>>n;
    v.resize(n);
    for(int i=0; i<n; i++)
        f>>v[i];
}

int main()
{
    rd();
    int m, x, y;
    f>>m;
    for(int i=0; i<m; i++)
    {
        f>>x>>y;
        if(!x)
            g<<max_pos(y)<<'\n';
        else if(x==1)
            g<<less_than_x_max_pos(y)<<'\n';
        else
            g<<greater_than_x_min_pos(y)<<'\n';
    }
    cout<<v[20886];
    f.close();
    g.close();
    return 0;
}