View Code of Problem 134

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<string>
#include<set>
using namespace std;
const int N=100000+10;
int n,m,s[N];
struct node
{
    int l,r,n;
} a[N<<2];
void build(int l,int r,int k)
{
    a[k].l=l,a[k].r=r;
    if(l==r)
    {
        a[k].n=s[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,2*k);
    build(mid+1,r,2*k+1);
    a[k].n=min(a[k*2].n,a[k*2+1].n);
}
int query(int l,int r,int k)
{
    if(a[k].l==l&&a[k].r==r)
        return a[k].n;
    int mid=(a[k].l+a[k].r)/2;
    if(l>mid)return query(l,r,k*2+1);
    if(r<=mid)return query(l,r,2*k);
    return min(query(l,mid,2*k),query(mid+1,r,2*k+1));
}
int main()
{
    while(cin>>n)
    {
        for(int i=1; i<=n; i++)
            cin>>s[i];
        build(1,n,1);
        cin>>m;
        while(m--)
        {
            int a,b;
            cin>>a>>b;
            if(a==b)
                cout<<s[a]<<endl;
            else
                cout<<query(a,b,1)<<endl;
        }
    }
    return 0;
}