#include <limits>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstdint>

#if __cplusplus >= 201703
#define IF_CONSTEXPR if constexpr
#else
#define IF_CONSTEXPR if
#endif

template<class T>
using should_move = std::is_same<T, std::remove_reference_t<T>>; // same trick as std::forward does

template<class T>
T&& forward_subpart(T&& value, std::true_type whether_should_move) {
  return std::move(value);
}

template<class T>
T&& forward_subpart(T&& value, std::false_type whether_should_move) {
  return value;
}

uint64_t msb64(uint64_t x) {
  x |= (x >> 1);
  x |= (x >> 2);
  x |= (x >> 4);
  x |= (x >> 8);
  x |= (x >> 16);
  x |= (x >> 32);
  return x & ~(x >> 1);
}

template<class Monoid>
struct SegmentTree {
  // This layout is intentional:
  // we need the constants to be initialized when constructing store,
  // at the same time the overhead incurred by such layout is expected to be
  // order of magnitude less than the overall footprint in typical usage.

  const size_t lowest_layer_idx;
  const size_t lowest_layer_begin;
  std::vector<Monoid> store;

  template<class Cont>
  SegmentTree(Cont&& cont)
    : lowest_layer_idx(std::ceil(std::log2(cont.size())))
    , lowest_layer_begin(1 << lowest_layer_idx) // derived from the formula of geometric progression sum; vertexes numbered from 1
    , store(lowest_layer_begin << 1) {
    IF_CONSTEXPR (should_move<Cont>::value) {
      std::move(std::begin(cont), std::end(cont), store.begin() + lowest_layer_begin);
    } else {
      std::copy(std::begin(cont), std::end(cont), store.begin() + lowest_layer_begin);
    }
    for (int idx = lowest_layer_begin - 1; idx > 0; --idx) {
      store[idx] = Monoid::combine(store[2 * idx], store[2 * idx + 1]);
    }
  }

  Monoid query(size_t left, size_t right) { // 1-based numeration, half-open range
    if (left < 1 || left >= right || right > lowest_layer_begin * 2) { return Monoid{}; };
    left -= 1, right -= 1;
    Monoid result;
    size_t span;
    for (uint64_t subsegment_begin = left; subsegment_begin < right; subsegment_begin += span) {
      size_t max_possible_span = (subsegment_begin ? subsegment_begin & -subsegment_begin : std::numeric_limits<size_t>::max());
      size_t max_allowed_span = msb64(right - subsegment_begin);
      span = std::min(max_possible_span, max_allowed_span);

      result = Monoid::combine(result, store[(lowest_layer_begin + subsegment_begin) / span]);
    }
    return result;
  }
};