#include <stdio.h>
#include <algorithm>
using namespace std;

#define N 1000000
#define INF 1000000000

int t[N];

int tree[4*N];

void build(int id, int l, int r) {
	if (l+1==r) tree[id]=t[l];
	else {
		int m=(l+r)/2;
		build(id*2,l,m);
		build(id*2+1,m,r);
		tree[id] = min(tree[id*2],tree[id*2+1]);
	}
}

void put(int id, int l, int r, int i, int v) {
	if (l+1==r) tree[id]=v;
	else {
		int m=(l+r)/2;
		if (i<m) put(id*2,l,m,i,v);
		else put(id*2+1,m,r,i,v);
		tree[id] = min(tree[id*2],tree[id*2+1]);
	}
}

int query(int id, int l, int r, int ql, int qr) {
	if (ql<=l && r<=qr) return tree[id];
	if (r<=ql || qr<=l) return INF;
	int m=(l+r)/2;
	return min(query(id*2,l,m,ql,qr), query(id*2+1,m,r,ql,qr));
}

int main() {
	int n=10;
	for (int i=0;i<n;i++) t[i]=rand()%10;
	for (int i=0;i<n;i++) printf("%d ",t[i]); printf("\n");
	build(1,0,n);
	for (int it=0;it<10;it++) {
		int i=rand()%n;
		int v=rand()%10;
		t[i]=v;
		put(1,0,n,i,v);
	}
	for (int i=0;i<n;i++) printf("%d ",t[i]); printf("\n");
	for (int it=0;it<10;it++) {
		int a=rand()%n, b=rand()%n;
		if (b<a) swap(a,b);
		int r=query(1,0,n,a,b+1);
		printf("[%d,%d] = %d\n",a,b,r);
	}
	return 0;
}