#include <cmath>
#include <algorithm>
using namespace std;

template <class T = int>
class RangeMinMaxQuery {
private:
  T **_table;
  bool _maxQ;
  unsigned long _n;
public:
  RangeMinMaxQuery(const unsigned long n, bool maxQuery) {
    this->_n = n;
    this->_maxQ = maxQuery;
    this->_table = new T*[this->_n];
    unsigned long limit = lrint(log2(this->_n)) + 1;
    for (unsigned long i = 0; i < this->_n; ++i) (this->_table)[i] = new T[limit];
  };
  RangeMinMaxQuery(const T a[], const unsigned long n, bool maxQuery) : RangeMinMaxQuery(n, maxQuery) {
    this->build(a);
  }
  void build(const T a[]) {
    for (unsigned long i = 0; i < this->_n; ++i) (this->_table)[i][0] = a[i];
    for (unsigned long expOf2 = 1, len; (len = (1 << expOf2)) <= this->_n; ++expOf2)
      for (unsigned long i = 0; i + len <= this->_n; ++i)
        (this->_table)[i][expOf2] = this->_maxQ?
        max((this->_table)[i][expOf2-1], (this->_table)[i+(1<<(expOf2-1))][expOf2-1]):
        min((this->_table)[i][expOf2-1], (this->_table)[i+(1<<(expOf2-1))][expOf2-1]);
  };
  // min/max query for [start; end] segment
  T query(const unsigned long start, const unsigned long end) {
    unsigned long length = end - start + 1;
    unsigned long expOf2 = lrint(floor(log2(length)));
    return this->_maxQ ? max((this->_table)[start][expOf2], (this->_table)[end-(1<<expOf2)+1][expOf2]) : min((this->_table)[start][expOf2], (this->_table)[end-(1<<expOf2)+1][expOf2]);
  };
  ~RangeMinMaxQuery() {
    for (unsigned long i = 0; i < this->_n; ++i) (this->_table)[i] = nullptr;
    this->_table = nullptr;
  }
};