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

#include <bits/stdc++.h>

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

using namespace std;

struct RangeTree {
	const static int root = 1;
	vector<int> b;
	int n;

	void calc( int v ) {
		b[v] = min(b[2 * v], b[2 * v + 1]);
	}
	int getM( int l, int r ) {
		return (l + r + 1) / 2;
	}

	// [l, r)
	void build( int v, int l, int r, int *a ) {
		printf("build: %d [%d..%d)\n", v, l, r);
		assert(v < (int)b.size());
		if (r - l == 1) {
			b[v] = a[l];
			return;
		}
		int m = getM(l, r);
		build(2 * v, l, m, a);
		build(2 * v + 1, m, r, a);
		calc(v);
	}

	void init( int n, int *a ) {
		b.resize(3 * n);
		this->n = n;
		build(root, 0, n, a);
	}

	// [vl, vr), [l, r)
	int getMin( int v, int vl, int vr, int l, int r ) {
		if (vr <= l || r <= vl) return INT_MAX;
		if (l <= vl && vr <= r)
			return b[v];
		int vm = getM(vl, vr);
		// push();
		return min(
			getMin(2 * v + 0, vl, vm, l, r),
			getMin(2 * v + 1, vm, vr, l, r)
		);
	}
	int getMin( int l, int r ) { // [l, r)
		return getMin(root, 0, n, l, r);
	}

	void set( int v, int vl, int vr, int i, int x ) {
		if (vr - vl == 1) {
			b[v] = x;
			return;
		}
		int vm = getM(vl, vr);
		// push();
		if (i < vm)
			set(2 * v + 0, vl, vm, i, x);
		else
			set(2 * v + 1, vm, vr, i, x);
		calc(v); // usual error is to forget this stuff =((
	}
	void set( int i, int x ) {
		set(root, 0, n, i, x);
	}
};

int main() {
	int n = 10;
	std::vector<int> a(n);
	for (int &x : a) x = rand();
	for (int &x : a) printf("%d ", x);
	puts("");
	RangeTree tree;
	tree.init(n, a.data());
	forn(r, n + 1) forn(l, r) {
		int f1 = tree.getMin(l, r);
		int f2 = *std::min_element(a.begin() + l, a.begin() + r);
		printf("[%d..%d) : tree=%d min_element=%d\n", l, r, f1, f2);
		assert(f1 == f2);
	}
}