#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;
}