#include <fstream>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int arr[100001];
int main()
{
    int n,q,a,o=0,u=0,x;
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>arr[i];
    }
    in>>q;
    for(int i=1; i<=q; i++)
    {
        in>>a>>x;
        int l=1;
        int h=n;
        if(a==0)
        {
            int ans=-1;
            while (l<=h)
            {
                int mid=(l+h)/2;
                if(arr[mid]==x){
                ans=mid;
                l=mid+1;
                }
                else if(arr[mid]>x){
                h=mid-1;
                }
                else{
                l=mid+1;
                }
            }
            out<<ans<<endl;

        }
        if(a==1){
     int ans=-1;
            while (l<=h)
            {
                int mid=(l+h)/2;
                if(arr[mid]<=x){
                ans=mid;
                l=mid+1;
                }
                else{
                h=mid-1;
                }
            }
            out<<ans<<endl;
        }
        if(a==2){
        int ans=-1;
            while (l<=h)
            {
                int mid=(l+h)/2;
                if(arr[mid]>=x){
                ans=mid;
                h=mid-1;
                }
                else{
                l=mid+1;
                }
            }
            out<<ans;
        }
    }
    return 0;
}