#include #include #include #define fi first #define se second using namespace std; typedef pair pii; int N, M, Q; int L[202020], R[202020]; int mn[808080], mx[808080]; void init(int id, int s, int e){ if (s == e){ mn[id] = L[s]; mx[id] = R[s]; return; } int m=s+e>>1; init(id*2, s, m), init(id*2+1, m+1, e); mn[id] = min(mn[id*2], mn[id*2+1]); mx[id] = max(mx[id*2], mx[id*2+1]); } pii rmq(int id, int s, int e, int ts, int te){ if (e < ts || te < s) return pii(N, 0); if (ts <= s && e <= te) return pii(mn[id], mx[id]); int m=s+e>>1; pii r1 = rmq(id*2, s, m, ts, te); pii r2 = rmq(id*2+1, m+1, e, ts, te); return pii(min(r1.fi, r2.fi), max(r1.se, r2.se)); } int main(){ scanf("%d %d", &N, &M); for (int i=1; i