#include <bits/stdc++.h>
using i64 = long long;
using namespace std;

const int N = 5e5 + 5;
int n, q, a[N], b[N];
i64 f[N][41];
vector<int> pos;
vector<i64> sum;
i64 cal(int len) { return 1ll * len * (len + 1) / 2; }
i64 query(int l, int r)
{
    if (l > r)
        return 1e18;
    i64 ret = 0;
    if (r - l + 1 <= 40)
        return f[l][r - l + 1];
    auto it1 = lower_bound(pos.begin(), pos.end(), l);
    if (it1 == pos.end() || *it1 > r)
        return cal(r - l + 1);
    ret = cal(*it1 - l + 1);
    int disl = it1 - pos.begin();
    auto itr = upper_bound(pos.begin(), pos.end(), r);
    assert(itr != pos.begin());
    itr = prev(itr);
    int disr = itr - pos.begin();
    assert(disl <= disr);
    ret += sum[disr] - sum[disl];
    if (*itr < r)
        ret += cal(r - *itr);
    return ret;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
        if (a[i] <= a[i + 1])
            b[i] = 1;
    for (int i = 1, pre = 0; i <= n; i++)
    {
        if (b[i])
            continue;
        pos.push_back(i);
        sum.push_back(cal(i - pre));
        pre = i;
    }
    for (int j = 1; j < pos.size(); j++)
        sum[j] += sum[j - 1];
    for (int i = 1; i <= n; i++)
    {
        int pre = i - 1;
        i64 sum = 0;
        for (int j = 1; j <= 40 && i + j - 1 <= n; j++)
        {
            if (!b[i + j - 1])
            {
                sum += cal(i + j - 1 - pre);
                pre = i + j - 1;
            }
            f[i][j] = sum;
            if (pre < i + j - 1)
                f[i][j] += cal(i + j - 1 - pre);
        }
    }

    while (q--)
    {
        int L, R;
        cin >> L >> R;
        if (L == R)
        {
            cout << 1 << '\n';
            continue;
        }
        int l = L, r = R, mid;
        while (l < r)
        {
            mid = l + r + 1 >> 1;
            i64 v = query(L, mid);
            i64 v1 = query(mid, R);
            if (v < v1)
                l = mid;
            else
                r = mid - 1;
        }
        cout << min(max(query(L, l), query(l, R)),
                    max(query(L, l + 1), query(l + 1, R)))
             << '\n';
    }
}