//Range query for minimum, point update
 
#include <algorithm>
 
using namespace std;
 
#define INF 2e9
#define NMAX 100010
#define TMAX ((1<<18)+10)	//size should be 2**(ceil(log2(N)) +1)
 
int A[NMAX];
 
int tree[TMAX];
int lookup[NMAX];
 
int N;
 
inline int left(int x){ return x*2+1; }
inline int right(int x) { return x*2+2; }
inline int parent(int x){ return (x+1)/2-1; }
 
void init(int node, int s, int e){
 
	if(s == e){
		tree[node] = A[s];
		lookup[s] = node;   		//lookup for bottom up update
		return;
	}
 
	int l,r,m;
	l = left(node), r = right(node) ,m = (s+e)/2;
 
	init(l,s,m);
	init(r,m+1,e);
 
	tree[node] = min(tree[l],tree[r]);
}
 
int query(int node, int s, int e, int i, int j){
 
	if(s > j || e < i) return INF;
	if(s >= i && e <= j) return tree[node];
 
	int l,r,m;
	l = left(node), r = right(node), m = (s+e)/2;
 
	return min(query(l,s,m,i,j),query(r,m+1,e,i,j));
}
 
 
 
void update(int i, int val){
	A[i] = val;
 
	int x = lookup[i];
	tree[x] = val;
 
	while(x){
		x = parent(x);
		tree[x] = min(tree[left(x)],tree[right(x)]);
	}
}
 
 
//calling query and init
 
void init(){
	init(0,0,N-1);
}
 
int query(int i, int j){
	return query(0,0,N-1,i,j);
}
 
 

Ly9SYW5nZSBxdWVyeSBmb3IgbWluaW11bSwgcG9pbnQgdXBkYXRlCgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgSU5GIDJlOQojZGVmaW5lIE5NQVggMTAwMDEwCiNkZWZpbmUgVE1BWCAoKDE8PDE4KSsxMCkJLy9zaXplIHNob3VsZCBiZSAyKiooY2VpbChsb2cyKE4pKSArMSkKCmludCBBW05NQVhdOwoKaW50IHRyZWVbVE1BWF07CmludCBsb29rdXBbTk1BWF07CgppbnQgTjsKCmlubGluZSBpbnQgbGVmdChpbnQgeCl7IHJldHVybiB4KjIrMTsgfQppbmxpbmUgaW50IHJpZ2h0KGludCB4KSB7IHJldHVybiB4KjIrMjsgfQppbmxpbmUgaW50IHBhcmVudChpbnQgeCl7IHJldHVybiAoeCsxKS8yLTE7IH0KCnZvaWQgaW5pdChpbnQgbm9kZSwgaW50IHMsIGludCBlKXsKCglpZihzID09IGUpewoJCXRyZWVbbm9kZV0gPSBBW3NdOwoJCWxvb2t1cFtzXSA9IG5vZGU7ICAgCQkvL2xvb2t1cCBmb3IgYm90dG9tIHVwIHVwZGF0ZQoJCXJldHVybjsKCX0KCglpbnQgbCxyLG07CglsID0gbGVmdChub2RlKSwgciA9IHJpZ2h0KG5vZGUpICxtID0gKHMrZSkvMjsKCglpbml0KGwscyxtKTsKCWluaXQocixtKzEsZSk7CgoJdHJlZVtub2RlXSA9IG1pbih0cmVlW2xdLHRyZWVbcl0pOwp9CgppbnQgcXVlcnkoaW50IG5vZGUsIGludCBzLCBpbnQgZSwgaW50IGksIGludCBqKXsKCglpZihzID4gaiB8fCBlIDwgaSkgcmV0dXJuIElORjsKCWlmKHMgPj0gaSAmJiBlIDw9IGopIHJldHVybiB0cmVlW25vZGVdOwoKCWludCBsLHIsbTsKCWwgPSBsZWZ0KG5vZGUpLCByID0gcmlnaHQobm9kZSksIG0gPSAocytlKS8yOwoKCXJldHVybiBtaW4ocXVlcnkobCxzLG0saSxqKSxxdWVyeShyLG0rMSxlLGksaikpOwp9CgoKCnZvaWQgdXBkYXRlKGludCBpLCBpbnQgdmFsKXsKCUFbaV0gPSB2YWw7CgoJaW50IHggPSBsb29rdXBbaV07Cgl0cmVlW3hdID0gdmFsOwoKCXdoaWxlKHgpewoJCXggPSBwYXJlbnQoeCk7CgkJdHJlZVt4XSA9IG1pbih0cmVlW2xlZnQoeCldLHRyZWVbcmlnaHQoeCldKTsKCX0KfQoKCi8vY2FsbGluZyBxdWVyeSBhbmQgaW5pdAoKdm9pZCBpbml0KCl7Cglpbml0KDAsMCxOLTEpOwp9CgppbnQgcXVlcnkoaW50IGksIGludCBqKXsKCXJldHVybiBxdWVyeSgwLDAsTi0xLGksaik7Cn0KCg==