/**
 * Sergey Kopeliovich (burunduk30@gmail.com)
 */

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < n; i++)

struct RangeTree {
	// root = 1
	int n;
	std::vector<int> b;

	void calc( int i ) {
		b[i] = std::min(b[2 * i], b[2 * i + 1]);
	}
	void init( std::vector<int> &a ) {
		n = a.size();
		b.resize(2 * n);
		copy(a.begin(), a.end(), b.begin() + n);
		for (int i = n - 1; i >= 1; i--)
			calc(i);
	}

	int min( int l, int r ) { // [l, r]
		int result = INT_MAX;
		for (l += n, r += n; l <= r; l /= 2, r /= 2) {
			if (l % 2 == 1) result = std::min(result, b[l++]);
			if (r % 2 == 0) result = std::min(result, b[r--]);
		}
		return result;
	}
	void set( int i, int x ) {
		i += n, b[i] = x;
		for (i /= 2; i >= 1; i /= 2)
			calc(i);
	}

	// O(log (R-L))
	// 2n
	// small constant (no recursion)
};

int main() {
	int n = 10;
	std::vector<int> a(n);
	for (int &x : a) x = rand();
	RangeTree tree;
	tree.init(a);
	forn(r, n) forn(l, r + 1)
		assert(tree.min(l, r) == *std::min_element(a.begin() + l, a.begin() + r + 1));
}