P1816 忠诚

#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 100005;
ll a[maxn],tree[(maxn)<<2+5];
ll ls(ll i){return i<<1;  }
ll rs(ll i){return i<<1|1;}
void push_up(int p){
    tree[p]=min(tree[ls(p)],tree[rs(p)]);
}
void build(ll p,ll pl,ll pr){
    if(pl==pr){
        tree[p]=a[pl];
        return;
    }
    ll mid=(pl+pr)>>1;
    build(ls(p),pl,mid  );
    build(rs(p),mid+1,pr);
    push_up(p);
}
ll query(ll l,ll r,ll p,ll pl,ll pr){      
    if(pr<l||r<pl)
        return 0;
    if(pl>=l&&r>=pr) 
        return tree[p];
    ll res1=maxn,res2=maxn;
    ll mid=(pl+pr)>>1;
    if(l<=mid) res1=min(res1,query(l,r,ls(p),pl,mid ));
    if(r>mid)  res2=min(res2,query(l,r,rs(p),mid+1,pr));
    return min(res1,res2);
}
int m,n,r,l;
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>m>>n;
    seq(i,1,m)
        cin>>a[i];
    build(1,1,n);
    seq(i,1,n){
        cin>>l>>r;
        cout<<query(l,r,1,1,n)<<" ";
    }
    return 0;
}