#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define INF (1 << 30)
#define mp make_pair
int n, q;
vector<int> p;
struct node_t{
int val;
node_t *lch, *rch;
int pri;
int cnt;
int mini;
node_t(int v) : val(v), cnt(1), mini(v){
pri = rand() % INF;
rch = lch = NULL;
}
};
int sol_count(node_t *t){ return !t ? 0 : t->cnt; }
int sol_mini(node_t *t){ return !t ? INF : t->mini; }
node_t *update(node_t *t){
t->cnt = sol_count(t->lch) + sol_count(t->rch) + 1;
t->mini = min(min(sol_mini(t->lch), sol_mini(t->rch)), t->val);
return t;
}
node_t *merge(node_t *l, node_t * r) {
if (!l || !r) return !l ? r : l;
if (l->pri > r->pri){
l->rch = merge(l->rch, r);
return update(l);
} else {
r->lch = merge(l, r->lch);
return update(r);
}
}
pair<node_t*, node_t*> split(node_t *t, int pos) {
if (!t) return mp((node_t*)NULL, (node_t*)NULL);
if (pos <= sol_count(t->lch)) {
pair<node_t*, node_t*> s = split(t->lch, pos);
t->lch = s.second;
return mp(s.first, update(t));
} else {
pair<node_t*, node_t*> s = split(t->rch, pos - sol_count(t->lch) - 1);
t->rch = s.first;
return mp(update(t), s.second);
}
}
node_t *insert(node_t *t, int pos, node_t *n) {
pair<node_t*, node_t*> s = split(t, pos - 1);
return merge(merge(s.first, n), s.second);
}
node_t *remove(node_t *t, int pos) {
pair<node_t*, node_t*> s;
s = split(t, pos - 1);
return merge(s.first, split(s.second, 1).second);
}
int minimum(node_t *t, int l, int r) {
int tmp;
pair<node_t*, node_t*> res1, res2;
res1 = split(t, l - 1);
res2 = split(res1.second, r - l + 1);
tmp = sol_mini(res2.first);
t = merge(res1.first, merge(res2.first, res2.second));
return tmp;
}
inline void output(node_t* v, int x, int y) { if(v != NULL && v->val >= x && v->val <= y) printf("%d\n", v->val); }
node_t* find_split_node(node_t* r, int x, int y) {
node_t* v = r;
while (v != NULL && !(v->lch == NULL && v->rch == NULL) && (v->val >= y || x > v->val)) {
output(v, x, y);
if(y <= v->val) v = v->lch;
else v = v->rch;
}
return v;
}
void repo(node_t* r) {
if(r == NULL) return ;
if(r->lch != NULL) repo(r->lch);
printf("%d\n", r->val);
if(r->rch != NULL) repo(r->rch);
}
void query(node_t *r, int x, int y) {
node_t* vs = find_split_node(r, x, y);
if(vs == NULL) return ;
output(vs, x, y);
if(vs->lch != NULL || vs->rch != NULL) {
node_t* v = vs->lch;
while(v != NULL && !(v->lch == NULL && v->rch == NULL)) {
output(v, x, y);
if(x <= v->val) {
repo(v->rch);
v = v->lch;
} else v = v->rch;
}
output(v, x, y);
v = vs->rch;
while(v != NULL && !(v->lch == NULL && v->rch == NULL)) {
output(v, x, y);
if(y <= v->val) v = v->lch;
else {
repo(v->lch);
v = v->rch;
}
}
output(v, x, y);
}
}
int main(){
scanf("%d %d", &n, &q);
srand((unsigned int) time(NULL));
p.resize(n);
rep(i, n) scanf("%d", &p[i]);
sort(p.begin(), p.end());
node_t root(p[0]);
node_t* u = &root;
for(int i = 1; i < n; ++i) u = insert(u, i + 1, new node_t(p[i]));
while(q--) {
puts("");
int a, b;
scanf("%d %d", &a, &b);
if(a > b) swap(a, b);
query(u, a, b);
}
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSByZXAoaSwgbikgZm9yKGludCBpID0gMDsgaSA8IChpbnQpbjsgaSsrKQojZGVmaW5lIElORiAoMSA8PCAzMCkKI2RlZmluZSBtcCBtYWtlX3BhaXIKIAppbnQgbiwgcTsKdmVjdG9yPGludD4gcDsKCnN0cnVjdCBub2RlX3R7CiAgICBpbnQgdmFsOwogICAgbm9kZV90ICpsY2gsICpyY2g7CiAgICBpbnQgcHJpOwogICAgaW50IGNudDsKICAgIGludCBtaW5pOwogICAgbm9kZV90KGludCB2KSA6IHZhbCh2KSwgY250KDEpLCBtaW5pKHYpewogICAgcHJpID0gcmFuZCgpICUgSU5GOwoJcmNoID0gbGNoID0gTlVMTDsKICAgIH0KfTsKCmludCBzb2xfY291bnQobm9kZV90ICp0KXsgcmV0dXJuICF0ID8gMCA6IHQtPmNudDsgfQppbnQgc29sX21pbmkobm9kZV90ICp0KXsgcmV0dXJuICF0ID8gSU5GIDogdC0+bWluaTsgfQoKbm9kZV90ICp1cGRhdGUobm9kZV90ICp0KXsKICAgIHQtPmNudCA9IHNvbF9jb3VudCh0LT5sY2gpICsgc29sX2NvdW50KHQtPnJjaCkgKyAxOwogICAgdC0+bWluaSA9IG1pbihtaW4oc29sX21pbmkodC0+bGNoKSwgc29sX21pbmkodC0+cmNoKSksIHQtPnZhbCk7CiAgICByZXR1cm4gdDsKfQoKbm9kZV90ICptZXJnZShub2RlX3QgKmwsIG5vZGVfdCAqIHIpIHsKICAgIGlmICghbCB8fCAhcikgcmV0dXJuICFsID8gciA6IGw7CiAgICBpZiAobC0+cHJpID4gci0+cHJpKXsKCWwtPnJjaCA9IG1lcmdlKGwtPnJjaCwgcik7CglyZXR1cm4gdXBkYXRlKGwpOwogICAgfSBlbHNlIHsKCXItPmxjaCA9IG1lcmdlKGwsIHItPmxjaCk7CglyZXR1cm4gdXBkYXRlKHIpOwogICAgfQp9CgpwYWlyPG5vZGVfdCosIG5vZGVfdCo+IHNwbGl0KG5vZGVfdCAqdCwgaW50IHBvcykgewogICAgaWYgKCF0KSByZXR1cm4gbXAoKG5vZGVfdCopTlVMTCwgKG5vZGVfdCopTlVMTCk7IAogICAgaWYgKHBvcyA8PSBzb2xfY291bnQodC0+bGNoKSkgewoJcGFpcjxub2RlX3QqLCBub2RlX3QqPiBzID0gc3BsaXQodC0+bGNoLCBwb3MpOyAKCXQtPmxjaCA9IHMuc2Vjb25kOyAKCXJldHVybiBtcChzLmZpcnN0LCB1cGRhdGUodCkpOyAKICAgIH0gZWxzZSB7CglwYWlyPG5vZGVfdCosIG5vZGVfdCo+IHMgPSBzcGxpdCh0LT5yY2gsIHBvcyAtIHNvbF9jb3VudCh0LT5sY2gpIC0gMSk7Cgl0LT5yY2ggPSBzLmZpcnN0OwoJcmV0dXJuIG1wKHVwZGF0ZSh0KSwgcy5zZWNvbmQpOyAKICAgIH0KfQoKbm9kZV90ICppbnNlcnQobm9kZV90ICp0LCBpbnQgcG9zLCBub2RlX3QgKm4pIHsKICAgIHBhaXI8bm9kZV90Kiwgbm9kZV90Kj4gcyA9IHNwbGl0KHQsIHBvcyAtIDEpOwogICAgcmV0dXJuIG1lcmdlKG1lcmdlKHMuZmlyc3QsIG4pLCBzLnNlY29uZCk7Cn0KCm5vZGVfdCAqcmVtb3ZlKG5vZGVfdCAqdCwgaW50IHBvcykgewogICAgcGFpcjxub2RlX3QqLCBub2RlX3QqPiBzOwogICAgcyA9IHNwbGl0KHQsIHBvcyAtIDEpOwogICAgcmV0dXJuIG1lcmdlKHMuZmlyc3QsIHNwbGl0KHMuc2Vjb25kLCAxKS5zZWNvbmQpOwp9CgppbnQgbWluaW11bShub2RlX3QgKnQsIGludCBsLCBpbnQgcikgewogICAgaW50IHRtcDsKICAgIHBhaXI8bm9kZV90Kiwgbm9kZV90Kj4gcmVzMSwgcmVzMjsKICAgIHJlczEgPSBzcGxpdCh0LCBsIC0gMSk7CiAgICByZXMyID0gc3BsaXQocmVzMS5zZWNvbmQsIHIgLSBsICsgMSk7CiAgICB0bXAgPSBzb2xfbWluaShyZXMyLmZpcnN0KTsKICAgIHQgPSBtZXJnZShyZXMxLmZpcnN0LCBtZXJnZShyZXMyLmZpcnN0LCByZXMyLnNlY29uZCkpOwogICAgcmV0dXJuIHRtcDsKfQoKaW5saW5lIHZvaWQgb3V0cHV0KG5vZGVfdCogdiwgaW50IHgsIGludCB5KSB7IGlmKHYgIT0gTlVMTCAmJiB2LT52YWwgPj0geCAmJiB2LT52YWwgPD0geSkgcHJpbnRmKCIlZFxuIiwgdi0+dmFsKTsgfQoKbm9kZV90KiBmaW5kX3NwbGl0X25vZGUobm9kZV90KiByLCBpbnQgeCwgaW50IHkpIHsKICAgIG5vZGVfdCogdiA9IHI7CiAgICB3aGlsZSAodiAhPSBOVUxMICYmICEodi0+bGNoID09IE5VTEwgJiYgdi0+cmNoID09IE5VTEwpICYmICh2LT52YWwgPj0geSB8fCB4ID4gdi0+dmFsKSkgewoJb3V0cHV0KHYsIHgsIHkpOwoJaWYoeSA8PSB2LT52YWwpIHYgPSB2LT5sY2g7CgllbHNlIHYgPSB2LT5yY2g7CiAgICB9CiAgICByZXR1cm4gdjsKfQoKdm9pZCByZXBvKG5vZGVfdCogcikgewogICAgaWYociA9PSBOVUxMKSByZXR1cm4gOwogICAgaWYoci0+bGNoICE9IE5VTEwpIHJlcG8oci0+bGNoKTsKICAgIHByaW50ZigiJWRcbiIsIHItPnZhbCk7CiAgICBpZihyLT5yY2ggIT0gTlVMTCkgcmVwbyhyLT5yY2gpOwp9Cgp2b2lkIHF1ZXJ5KG5vZGVfdCAqciwgaW50IHgsIGludCB5KSB7CiAgICBub2RlX3QqIHZzID0gZmluZF9zcGxpdF9ub2RlKHIsIHgsIHkpOwogICAgaWYodnMgPT0gTlVMTCkgcmV0dXJuIDsKICAgIG91dHB1dCh2cywgeCwgeSk7CgogICAgaWYodnMtPmxjaCAhPSBOVUxMIHx8IHZzLT5yY2ggIT0gTlVMTCkgewoJbm9kZV90KiB2ID0gdnMtPmxjaDsKCXdoaWxlKHYgIT0gTlVMTCAmJiAhKHYtPmxjaCA9PSBOVUxMICYmIHYtPnJjaCA9PSBOVUxMKSkgewoJICAgIG91dHB1dCh2LCB4LCB5KTsKCSAgICBpZih4IDw9IHYtPnZhbCkgewoJCXJlcG8odi0+cmNoKTsKCQl2ID0gdi0+bGNoOwoJICAgIH0gZWxzZSB2ID0gdi0+cmNoOwoJfQoJb3V0cHV0KHYsIHgsIHkpOwoKCXYgPSB2cy0+cmNoOwoJd2hpbGUodiAhPSBOVUxMICYmICEodi0+bGNoID09IE5VTEwgJiYgdi0+cmNoID09IE5VTEwpKSB7CgkgICAgb3V0cHV0KHYsIHgsIHkpOwoJICAgIGlmKHkgPD0gdi0+dmFsKSB2ID0gdi0+bGNoOwoJICAgIGVsc2UgewoJCXJlcG8odi0+bGNoKTsKCQl2ID0gdi0+cmNoOwoJICAgIH0KCX0KCW91dHB1dCh2LCB4LCB5KTsKICAgIH0KfQoKaW50IG1haW4oKXsKICAgIHNjYW5mKCIlZCAlZCIsICZuLCAmcSk7CiAgICBzcmFuZCgodW5zaWduZWQgaW50KSB0aW1lKE5VTEwpKTsKICAgIHAucmVzaXplKG4pOwogICAgcmVwKGksIG4pIHNjYW5mKCIlZCIsICZwW2ldKTsKICAgIHNvcnQocC5iZWdpbigpLCBwLmVuZCgpKTsKICAgIG5vZGVfdCByb290KHBbMF0pOwogICAgbm9kZV90KiB1ID0gJnJvb3Q7CiAgICBmb3IoaW50IGkgPSAxOyBpIDwgbjsgKytpKSB1ID0gaW5zZXJ0KHUsIGkgKyAxLCBuZXcgbm9kZV90KHBbaV0pKTsKICAgIAogICAgd2hpbGUocS0tKSB7CglwdXRzKCIiKTsKCWludCBhLCBiOwoJc2NhbmYoIiVkICVkIiwgJmEsICZiKTsKCWlmKGEgPiBiKSBzd2FwKGEsIGIpOwoJcXVlcnkodSwgYSwgYik7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==