#include <bits/stdc++.h>

using namespace std;


int n, v[100003];
int main()
{
    int i, left , tests, right, mij, j, vt, val;
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    cin >> n;
    for(i = 1; i <= n; i++)
        cin >> v[i];
    cin >> tests;
    for(j = 1; j <= tests; j++)
    { cin >> vt >> val;
    left = 1;
    right = n;
    if( vt == 0)
     {while( left <= right )
        {
            mij = left + (right - left) / 2;
            if(val == v[mij] )
            {   while( v[mij] ==  val and mij <= n)
                mij++;
                cout << mij - 1 << " ";
                break;
            }
            else
                if( val < v[mij] )
                 {
                     right = mij - 1;

                 }
                 else
                 {
                     left = mij + 1;
                 }
              if( left > right)
                    cout << -1 << " ";
            }
     }
                 else
                    if(vt == 1)
                    {while( left <= right )
                       {
                        mij = left + (right - left) / 2;
                        if( v[mij] <= val)
                        {
                            while( v[mij] <= val and mij <= n)
                                mij++;
                            cout << mij - 1 << " ";
                            break;
                        }
                        else
                            if(v[mij] > val)
                            right = mij - 1;

                         }
                    }
                    else
                        if(vt == 2)
                    {    while( left <= right)
                       {
                        mij = left + (right - left) / 2;
                        if(v[mij] >= val)
                        {while(v[mij] >= val and mij >= 0)
                                mij--;
                          cout << mij + 1 << " ";
                          break;
                        }
                        else
                            if(v[mij] < val)
                            left = mij + 1;
                        }
                    }
    }
    return 0;
}