#include <bits/stdc++.h>
#define clr(x) memset((x), 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define in(x) int (x); input((x));
#define x first
#define y second
#define forn(i, n) for(int i = 0; i < (int)(n); ++i)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; --i)
#define for1(i, n) for(int i = 1; i <= (int)(n); ++i)
typedef int itn;
#define next next12345
#define prev prev12345
#define left lefdsf232
#define right rig43783
#define x1 x12345
#define y1 y12345
using namespace std;
template<typename T>
T gcd(T x, T y) {
while (y > 0) {
x %= y;
swap(x, y);
}
return x;
}
template<class T>
T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
template<class _T>
inline _T sqr(const _T &x) {
return x * x;
}
template<class _T>
inline string tostr(const _T &a) {
ostringstream os("");
os << a;
return os.str();
}
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const ld PI = 3.1415926535897932384626433832795L;
template<typename T>
inline void input(T &a) {
static int ed;
a = 0;
while (!isdigit(ed = getchar()) && ed != '-') { }
char neg = 0;
if (ed == '-') {
neg = 1;
ed = getchar();
}
while (isdigit(ed)) {
a = 10 * a + ed - '0';
ed = getchar();
}
if (neg) a = -a;
}
template<typename T = int>
inline T nxt() {
T res;
input(res);
return res;
}
void myassert(bool v) {
assert(v);
//cout << "FAIL\n";
//exit(0);
}
mt19937 generator;
bool check(int v) {
if (v < 2) return false;
for (int i = 2; i * i <= v; ++i) {
if (v % i == 0) {
return false;
}
}
return true;
}
long long pw(long long a, long long n, long long m) {
ll res = 1;
while (n) {
if (n & 1ll) {
res = res * a % m;
}
a = a * a % m;
n >>= 1;
}
return res;
}
long long inv(long long a, long long p) {
long long res = 1;
while (a > 1) {
res = res * (p - p / a) % p;
a = p % a;
}
return res;
}
struct F {
vector <int> a;
F(int n) {
a.resize(n);
}
int get(int r) {
int res = 0;
for (; r >= 0; r &= r + 1, --r) {
res += a[r];
}
return res;
}
void inc(int r) {
for (; r < a.size(); r |= r + 1)
a[r] += 1;
}
};
bool uax(int &x, int y) {
if (y > x) {
x = y;
return true;
}
return false;
}
bool uin(int &x, int y) {
if (y < x) {
x = y;
return true;
}
return false;
}
struct vertex {
vertex * l, * r;
ll sum;
vertex (ll val)
: l(NULL), r(NULL), sum(val)
{ }
vertex (vertex * l, vertex * r)
: l(l), r(r), sum(0)
{
if (l) sum += l->sum;
if (r) sum += r->sum;
}
};
vertex * build (int tl, int tr) {
if (tr - tl == 1)
return new vertex (0ll);
int tm = (tl + tr) / 2;
return new vertex (
build (tl, tm),
build (tm, tr)
);
}
ll get_sum (vertex * t, int tl, int tr, int l, int r) {
if (l >= r)
return 0;
if (l == tl && tr == r)
return t->sum;
int tm = (tl + tr) / 2;
return get_sum (t->l, tl, tm, l, min(r,tm))
+ get_sum (t->r, tm, tr, max(l,tm), r);
}
vertex * update (vertex * t, int tl, int tr, int pos, int new_val) {
if (tr - tl == 1)
return new vertex (new_val + t->sum);
int tm = (tl + tr) / 2;
if (pos < tm)
return new vertex (
update (t->l, tl, tm, pos, new_val),
t->r
);
else
return new vertex (
t->l,
update (t->r, tm, tr, pos, new_val)
);
}
void solve(int test) {
int n = nxt();
int m = nxt();
int a[n];
int b[n + 1];
forn(i, n) {
a[i] = nxt();
b[i] = a[i];
}
b[n] = 1;
sort(b, b + n + 1);
int s = unique(b, b + n + 1) - b;
vertex * data[n + 1];
data[0] = build(0, s);
for (int i = 0; i < n; ++i) {
int pos = lower_bound(b, b + s, a[i]) - b;
data[i + 1] = update(data[i], 0, s, pos, b[pos]);
}
// cerr << get_sum(data[n], 0, s, 0, 1) - get_sum(data[0], 0, s, 0, 1) << endl;
while (m--) {
int l = nxt() - 1;
int r = nxt();
int prev = 0;
ll sum = 0;
while (true) {
int pos = upper_bound(b, b + s, min(sum + 1, 1ll * INT_MAX)) - b;
if (pos == prev) {
break;
}
sum = get_sum(data[r], 0, s, prev, pos) - get_sum(data[l], 0, s, prev, pos);
prev = pos;
}
cout << sum + 1 << "\n";
}
}
int main(int argc, char ** argv) {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#else
#define fname "sequence"
//freopen(fname".in", "r", stdin);
//freopen(fname".out", "w", stdout);
#endif
//ios_base::sync_with_stdio(false);
// pre();
// test();
// exit(0);
int t = 1;
#ifdef LOCAL
#else
#endif
int c = 0;
while (t--) {
solve(++c);
}
#ifdef LOCAL
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIGNscih4KSBtZW1zZXQoKHgpLCAwLCBzaXplb2YoeCkpCiNkZWZpbmUgYWxsKHgpICh4KS5iZWdpbigpLCAoeCkuZW5kKCkKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBpbih4KSBpbnQgKHgpOyBpbnB1dCgoeCkpOwojZGVmaW5lIHggZmlyc3QKI2RlZmluZSB5IHNlY29uZAojZGVmaW5lIGZvcm4oaSwgbikgZm9yKGludCBpID0gMDsgaSA8IChpbnQpKG4pOyArK2kpCiNkZWZpbmUgZm9yZChpLCBuKSBmb3IoaW50IGkgPSAoaW50KShuKSAtIDE7IGkgPj0gMDsgLS1pKQojZGVmaW5lIGZvcjEoaSwgbikgZm9yKGludCBpID0gMTsgaSA8PSAoaW50KShuKTsgKytpKQoKdHlwZWRlZiBpbnQgaXRuOwoKI2RlZmluZSBuZXh0IG5leHQxMjM0NQojZGVmaW5lIHByZXYgcHJldjEyMzQ1CiNkZWZpbmUgbGVmdCBsZWZkc2YyMzIKI2RlZmluZSByaWdodCByaWc0Mzc4MwojZGVmaW5lIHgxIHgxMjM0NQojZGVmaW5lIHkxIHkxMjM0NQoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnRlbXBsYXRlPHR5cGVuYW1lIFQ+ClQgZ2NkKFQgeCwgVCB5KSB7CiAgICB3aGlsZSAoeSA+IDApIHsKICAgICAgICB4ICU9IHk7CiAgICAgICAgc3dhcCh4LCB5KTsKICAgIH0KICAgIHJldHVybiB4Owp9Cgp0ZW1wbGF0ZTxjbGFzcyBUPgpUIGxjbShUIGEsIFQgYikgewogICAgcmV0dXJuIGEgLyBnY2QoYSwgYikgKiBiOwp9CgoKdGVtcGxhdGU8Y2xhc3MgX1Q+CmlubGluZSBfVCBzcXIoY29uc3QgX1QgJngpIHsKICAgIHJldHVybiB4ICogeDsKfQoKdGVtcGxhdGU8Y2xhc3MgX1Q+CmlubGluZSBzdHJpbmcgdG9zdHIoY29uc3QgX1QgJmEpIHsKICAgIG9zdHJpbmdzdHJlYW0gb3MoIiIpOwogICAgb3MgPDwgYTsKICAgIHJldHVybiBvcy5zdHIoKTsKfQoKdHlwZWRlZiBsb25nIGRvdWJsZSBsZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBQSUk7CmNvbnN0IGxkIFBJID0gMy4xNDE1OTI2NTM1ODk3OTMyMzg0NjI2NDMzODMyNzk1TDsKCnRlbXBsYXRlPHR5cGVuYW1lIFQ+CmlubGluZSB2b2lkIGlucHV0KFQgJmEpIHsKICAgIHN0YXRpYyBpbnQgZWQ7CiAgICBhID0gMDsKICAgIHdoaWxlICghaXNkaWdpdChlZCA9IGdldGNoYXIoKSkgJiYgZWQgIT0gJy0nKSB7IH0KICAgIGNoYXIgbmVnID0gMDsKICAgIGlmIChlZCA9PSAnLScpIHsKICAgICAgICBuZWcgPSAxOwogICAgICAgIGVkID0gZ2V0Y2hhcigpOwogICAgfQogICAgd2hpbGUgKGlzZGlnaXQoZWQpKSB7CiAgICAgICAgYSA9IDEwICogYSArIGVkIC0gJzAnOwogICAgICAgIGVkID0gZ2V0Y2hhcigpOwogICAgfQogICAgaWYgKG5lZykgYSA9IC1hOwp9Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBUID0gaW50PgppbmxpbmUgVCBueHQoKSB7CiAgICBUIHJlczsKICAgIGlucHV0KHJlcyk7CiAgICByZXR1cm4gcmVzOwp9Cgp2b2lkIG15YXNzZXJ0KGJvb2wgdikgewogICAgYXNzZXJ0KHYpOwogICAgLy9jb3V0IDw8ICJGQUlMXG4iOwogICAgLy9leGl0KDApOwp9CgptdDE5OTM3IGdlbmVyYXRvcjsKCmJvb2wgY2hlY2soaW50IHYpIHsKICAgIGlmICh2IDwgMikgcmV0dXJuIGZhbHNlOwogICAgZm9yIChpbnQgaSA9IDI7IGkgKiBpIDw9IHY7ICsraSkgewogICAgICAgIGlmICh2ICUgaSA9PSAwKSB7CiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gdHJ1ZTsKfQoKbG9uZyBsb25nIHB3KGxvbmcgbG9uZyBhLCBsb25nIGxvbmcgbiwgbG9uZyBsb25nIG0pIHsKICAgIGxsIHJlcyA9IDE7CiAgICB3aGlsZSAobikgewogICAgICAgIGlmIChuICYgMWxsKSB7CiAgICAgICAgICAgIHJlcyA9IHJlcyAqIGEgJSBtOwogICAgICAgIH0KICAgICAgICBhID0gYSAqIGEgJSBtOwogICAgICAgIG4gPj49IDE7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9Cgpsb25nIGxvbmcgaW52KGxvbmcgbG9uZyBhLCBsb25nIGxvbmcgcCkgewogICAgbG9uZyBsb25nIHJlcyA9IDE7CiAgICB3aGlsZSAoYSA+IDEpIHsKICAgICAgICByZXMgPSByZXMgKiAocCAtIHAgLyBhKSAlIHA7CiAgICAgICAgYSA9IHAgJSBhOwogICAgfQogICAgcmV0dXJuIHJlczsKfQoKc3RydWN0IEYgewogICAgdmVjdG9yIDxpbnQ+IGE7CgogICAgRihpbnQgbikgewogICAgICAgIGEucmVzaXplKG4pOwogICAgfQoKICAgIGludCBnZXQoaW50IHIpIHsKICAgICAgICBpbnQgcmVzID0gMDsKICAgICAgICBmb3IgKDsgciA+PSAwOyByICY9IHIgKyAxLCAtLXIpIHsKICAgICAgICAgICAgcmVzICs9IGFbcl07CiAgICAgICAgfQogICAgICAgIHJldHVybiByZXM7CiAgICB9CgogICAgdm9pZCBpbmMoaW50IHIpIHsKICAgICAgICBmb3IgKDsgciA8IGEuc2l6ZSgpOyByIHw9IHIgKyAxKQogICAgICAgICAgICBhW3JdICs9IDE7CiAgICB9Cn07Cgpib29sIHVheChpbnQgJngsIGludCB5KSB7CiAgICBpZiAoeSA+IHgpIHsKICAgICAgICB4ID0geTsKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKYm9vbCB1aW4oaW50ICZ4LCBpbnQgeSkgewogICAgaWYgKHkgPCB4KSB7CiAgICAgICAgeCA9IHk7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CiAgICByZXR1cm4gZmFsc2U7Cn0KCgpzdHJ1Y3QgdmVydGV4IHsKICAgIHZlcnRleCAqIGwsICogcjsKICAgIGxsIHN1bTsKCiAgICB2ZXJ0ZXggKGxsIHZhbCkKICAgICAgICAgICAgOiBsKE5VTEwpLCByKE5VTEwpLCBzdW0odmFsKQogICAgeyB9CgogICAgdmVydGV4ICh2ZXJ0ZXggKiBsLCB2ZXJ0ZXggKiByKQogICAgICAgICAgICA6IGwobCksIHIociksIHN1bSgwKQogICAgewogICAgICAgIGlmIChsKSAgc3VtICs9IGwtPnN1bTsKICAgICAgICBpZiAocikgIHN1bSArPSByLT5zdW07CiAgICB9Cn07Cgp2ZXJ0ZXggKiBidWlsZCAoaW50IHRsLCBpbnQgdHIpIHsKICAgIGlmICh0ciAtIHRsID09IDEpCiAgICAgICAgcmV0dXJuIG5ldyB2ZXJ0ZXggKDBsbCk7CiAgICBpbnQgdG0gPSAodGwgKyB0cikgLyAyOwogICAgcmV0dXJuIG5ldyB2ZXJ0ZXggKAogICAgICAgICAgICBidWlsZCAodGwsIHRtKSwKICAgICAgICAgICAgYnVpbGQgKHRtLCB0cikKICAgICk7Cn0KCmxsIGdldF9zdW0gKHZlcnRleCAqIHQsIGludCB0bCwgaW50IHRyLCBpbnQgbCwgaW50IHIpIHsKICAgIGlmIChsID49IHIpCiAgICAgICAgcmV0dXJuIDA7CiAgICBpZiAobCA9PSB0bCAmJiB0ciA9PSByKQogICAgICAgIHJldHVybiB0LT5zdW07CiAgICBpbnQgdG0gPSAodGwgKyB0cikgLyAyOwogICAgcmV0dXJuIGdldF9zdW0gKHQtPmwsIHRsLCB0bSwgbCwgbWluKHIsdG0pKQogICAgICAgICAgICsgZ2V0X3N1bSAodC0+ciwgdG0sIHRyLCBtYXgobCx0bSksIHIpOwp9Cgp2ZXJ0ZXggKiB1cGRhdGUgKHZlcnRleCAqIHQsIGludCB0bCwgaW50IHRyLCBpbnQgcG9zLCBpbnQgbmV3X3ZhbCkgewogICAgaWYgKHRyIC0gdGwgPT0gMSkKICAgICAgICByZXR1cm4gbmV3IHZlcnRleCAobmV3X3ZhbCArIHQtPnN1bSk7CiAgICBpbnQgdG0gPSAodGwgKyB0cikgLyAyOwogICAgaWYgKHBvcyA8IHRtKQogICAgICAgIHJldHVybiBuZXcgdmVydGV4ICgKICAgICAgICAgICAgICAgIHVwZGF0ZSAodC0+bCwgdGwsIHRtLCBwb3MsIG5ld192YWwpLAogICAgICAgICAgICAgICAgdC0+cgogICAgICAgICk7CiAgICBlbHNlCiAgICAgICAgcmV0dXJuIG5ldyB2ZXJ0ZXggKAogICAgICAgICAgICAgICAgdC0+bCwKICAgICAgICAgICAgICAgIHVwZGF0ZSAodC0+ciwgdG0sIHRyLCBwb3MsIG5ld192YWwpCiAgICAgICAgKTsKfQoKCgp2b2lkIHNvbHZlKGludCB0ZXN0KSB7CiAgICBpbnQgbiA9IG54dCgpOwogICAgaW50IG0gPSBueHQoKTsKCiAgICBpbnQgYVtuXTsKICAgIGludCBiW24gKyAxXTsKICAgIGZvcm4oaSwgbikgewogICAgICAgIGFbaV0gPSBueHQoKTsKICAgICAgICBiW2ldID0gYVtpXTsKICAgIH0KICAgIGJbbl0gPSAxOwogICAgc29ydChiLCBiICsgbiArIDEpOwoKICAgIGludCBzID0gdW5pcXVlKGIsIGIgKyBuICsgMSkgLSBiOwoKICAgIHZlcnRleCAqIGRhdGFbbiArIDFdOwogICAgZGF0YVswXSA9IGJ1aWxkKDAsIHMpOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgaW50IHBvcyA9IGxvd2VyX2JvdW5kKGIsIGIgKyBzLCBhW2ldKSAtIGI7CiAgICAgICAgZGF0YVtpICsgMV0gPSB1cGRhdGUoZGF0YVtpXSwgMCwgcywgcG9zLCBiW3Bvc10pOwogICAgfQoKLy8gICAgY2VyciA8PCBnZXRfc3VtKGRhdGFbbl0sIDAsIHMsIDAsIDEpIC0gZ2V0X3N1bShkYXRhWzBdLCAwLCBzLCAwLCAxKSA8PCBlbmRsOwoKICAgIHdoaWxlIChtLS0pIHsKICAgICAgICBpbnQgbCA9IG54dCgpIC0gMTsKICAgICAgICBpbnQgciA9IG54dCgpOwoKICAgICAgICBpbnQgcHJldiA9IDA7CiAgICAgICAgbGwgc3VtID0gMDsKICAgICAgICB3aGlsZSAodHJ1ZSkgewogICAgICAgICAgICBpbnQgcG9zID0gdXBwZXJfYm91bmQoYiwgYiArIHMsIG1pbihzdW0gKyAxLCAxbGwgKiBJTlRfTUFYKSkgLSBiOwogICAgICAgICAgICBpZiAocG9zID09IHByZXYpIHsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHN1bSA9IGdldF9zdW0oZGF0YVtyXSwgMCwgcywgcHJldiwgcG9zKSAtIGdldF9zdW0oZGF0YVtsXSwgMCwgcywgcHJldiwgcG9zKTsKICAgICAgICAgICAgcHJldiA9IHBvczsKICAgICAgICB9CgogICAgICAgIGNvdXQgPDwgc3VtICsgMSA8PCAiXG4iOwogICAgfQp9CgoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKiogYXJndikgewoKI2lmZGVmIExPQ0FMCiAgICBmcmVvcGVuKCJpbnB1dC50eHQiLCAiciIsIHN0ZGluKTsKLy8gICAgZnJlb3Blbigib3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKI2Vsc2UKICAgICNkZWZpbmUgZm5hbWUgInNlcXVlbmNlIgogICAgLy9mcmVvcGVuKGZuYW1lIi5pbiIsICJyIiwgc3RkaW4pOwogICAgLy9mcmVvcGVuKGZuYW1lIi5vdXQiLCAidyIsIHN0ZG91dCk7CiNlbmRpZgogICAgLy9pb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKLy8gICAgcHJlKCk7Ci8vICAgIHRlc3QoKTsKLy8gICAgZXhpdCgwKTsKICAgIGludCB0ID0gMTsKCiNpZmRlZiBMT0NBTAojZWxzZQojZW5kaWYKICAgIGludCBjID0gMDsKCiAgICB3aGlsZSAodC0tKSB7CiAgICAgICAgc29sdmUoKytjKTsKICAgIH0KCiNpZmRlZiBMT0NBTAogICAgY2VyciA8PCAiVGltZSBlbGFwc2VkOiAiIDw8IDEuMCAqIGNsb2NrKCkgLyBDTE9DS1NfUEVSX1NFQyAqIDEwMDAgPDwgIiBtcy4iIDw8IGVuZGw7CiNlbmRpZgogICAgcmV0dXJuIDA7Cn0=