#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    vector<int> nums;
    int n;
    cin>>n;
    nums.reserve(n);
    for(int i=0;i<n;++i)
        cin>>nums[i];
    
    int m;
    cin>>m;
    
    int mode,el,l,r,mid,ans;
    for(int d=0;d<m;++d)
    {
        cin>>mode>>el;
        l=0;
        r=n-1;
        if(mode==0)
        {
            ans=-2;
            while(l<=r)
            {
                mid=l+(r-l)/2;
                if(nums[mid]<el)
                {
                    l=mid+1;
                }
                if(nums[mid]==el)
                {
                    ans=mid;
                    l=mid+1;
                }
                if(nums[mid]>el)
                {
                    r=mid-1;
                }
            }
            cout<<ans+1<<'\n';
        }
        if(mode==1)
        {
            ans=0;
            while(l<=r)
            {
                mid=l+(r-l)/2;
                if(nums[mid]<=el)
                {
                    l=mid+1;
                    ans=max(ans,mid);
                }
                if(nums[mid]>el)
                {
                    r=mid-1;
                }
            }
            cout<<ans+1<<'\n';
        }
        if(mode==2)
        {
            ans=n;
            while(l<=r)
            {
                mid=l+(r-l)/2;
                if(nums[mid]>=el)
                {
                    r=mid-1;
                    ans=min(ans,mid);
                }
                if(nums[mid]<el)
                {
                    l=mid+1;
                }
            }
            cout<<ans+1<<'\n';
        }
    }





    return 0;
}