Problem: Write a program which manipulates a sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$ by the following operations:

* min($b, e$): report the minimum element in $a_b, a_{b+1}, ..., a_{e-1}$
* max($b, e$): report the maximum element in $a_b, a_{b+1}, ..., a_{e-1}$

Constraints

* $1 \leq n \leq 1,000$
* $-1,000,000,000 \leq a_i \leq 1,000,000,000$
* $1 \leq q \leq 1,000$
* $0 \leq b < e \leq n$

Input

The input is given in the following format.


$n$
$a_0 \; a_1, ..., \; a_{n-1}$
$q$
$com_1 \; b_1 \; e_1$
$com_2 \; b_2 \; e_2$
:
$com_{q} \; b_{q} \; e_{q}$


In the first line, $n$ (the number of elements in $A$) is given. In the second line, $a_i$ (each element in $A$) are given. In the third line, the number of queries $q$ is given and each query is given in the following $q$ lines. $com_i$ denotes a type of query. 0 and 1 represents min($b, e$) and max($b, e$) respectively.

Output

For each query, print the minimum element or the maximum element in a line.

Example

Input

7
8 3 7 1 9 1 4
3
0 0 3
0 1 5
1 0 7


Output

3
1
9

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ld> vld;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); ++i)
#define TS to_string
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define endl "\n"

ll INF = 1e9;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}

//-----------------------------------------
class segment_tree_min{
  private:
    ll N = 1;
    vector<ll> data;
    ll def = LINF;
  public:

    segment_tree_min(vector<ll> vec){
      ll m = vec.size();
      while(N < m) N *= 2;
      data.resize(2*N, def);

      for(int i=0;i<m;i++) update(i,vec[i]);
    }

    void update(ll k, ll a){
      k += N - 1;
      data[k] = a;
      while(k > 0){
        k = (k-1) / 2;
        data[k] = min(data[k * 2 + 1] ,  data[k * 2 + 2]);
      }
    }

    // [a,b) のクエリを処理する
    ll query_(ll a, ll b, ll k, ll l, ll r){
      // [a,b)　と [l,r) が交差しない時
      if(r <= a || b <= l) return def; 

      // 完全に含まれている時
      if(a <= l && r <= b) return data[k];
      else{
        ll mid = (l + r) / 2;
        // 2つの子の最小値
        ll vl = query_(a,b,k*2+1,l,mid);
        ll vr = query_(a,b,k*2+2,mid,r);
        return min(vl , vr);
      }
    }

    ll query(ll a, ll b){
      return query_(a, b, 0, 0, N);
    }
};

class segment_tree_max{
  private:
    ll N = 1;
    vector<ll> data;
    ll def = -LINF;
  public:

    segment_tree_max(vector<ll> vec){
      ll m = vec.size();
      while(N < m) N *= 2;
      data.resize(2*N, def);

      for(int i=0;i<m;i++) update(i,vec[i]);
    }

    void update(ll k, ll a){
      k += N - 1;
      data[k] = a;
      while(k > 0){
        k = (k-1) / 2;
        data[k] = max(data[k * 2 + 1] ,  data[k * 2 + 2]);
      }
    }

    // [a,b) のクエリを処理する
    ll query_(ll a, ll b, ll k, ll l, ll r){
      // [a,b)　と [l,r) が交差しない時
      if(r <= a || b <= l) return def; 

      // 完全に含まれている時
      if(a <= l && r <= b) return data[k];
      else{
        ll mid = (l + r) / 2;
        // 2つの子の最小値
        ll vl = query_(a,b,k*2+1,l,mid);
        ll vr = query_(a,b,k*2+2,mid,r);
        return max(vl , vr);
      }
    }

    ll query(ll a, ll b){
      return query_(a, b, 0, 0, N);
    }
};
//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  ll n;
  cin >> n;
  vll a(n);
  REP(i,n) cin >> a[i];

  segment_tree_min mini(a);

  segment_tree_max maxi(a);

  ll q;
  cin >> q;
  REP(i,q){
    ll com;
    cin >> com;
    if(com == 0){
      ll b, e;
      cin >> b >> e;
      cout << mini.query(b,e) << endl;
    }
    else{
      ll b, e;
      cin >> b >> e;
      cout << maxi.query(b,e) << endl;
    }
  }
    
  return 0;
}