#include <bits/stdc++.h>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int nmax = 100005;
int N,M;
int a[nmax];



inline int CB0(int x)
{
    int st,dr,mid,ans = -1;
    st = 1; dr = N;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(a[mid] == x)
        {
            ans = mid;
            st = mid+1;
        }
        else if(a[mid] > x)
        {
            dr = mid-1;
        }
        else st = mid+1;
    }
    return ans;
}

inline int CB1(int x)
{
    int st,dr,mid,ans = 1;
    st = 1; dr = N;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(a[mid] <= x)
        {
            ans = mid;
            st = mid+1;
        }
        else if(a[mid] > x)
        {
            dr = mid-1;
        }
    }
    return ans;
}


inline int CB2(int x)
{
    int st,dr,mid,ans = N;
    st = 1; dr = N;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(a[mid] >= x)
        {
            ans = mid;
            dr = mid-1;
        }
        else st = mid+1;
    }
    return ans;
}




int main()
{
    int i,type,x;
    fin >> N;
    for(i = 1; i <=  N; i++)
        fin >> a[i];
    fin >> M;
    while(M--)
    {
       fin >> type >> x;
       if(type == 0) fout << CB0(x)<< "\n";
       else if(type == 1) fout << CB1(x)<<"\n";
       else fout << CB2(x) << "\n";
    }
    fout.close();
    return 0;
}