#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sz 200100
vector<ll>tr[4 * sz];
ll ar[sz];
void build(ll s, ll e, ll idx)
{
if (s == e)
{
tr[idx].push_back(ar[s]);
return;
}
ll m = (s + e) / 2;
build(s, m, 2 * idx);
build(m + 1, e, 2 * idx + 1);
merge(tr[2 * idx].begin(), tr[2 * idx].end(),
tr[2 * idx + 1].begin(), tr[2 * idx + 1].end(),
back_inserter(tr[idx]));
}
ll quelo(ll s, ll e, ll idx, ll qs, ll qe, ll v)
{
if (qs > e || qe < s || qs > qe)
return 0;
if (qs <= s && qe >= e)
return lower_bound(tr[idx].begin(), tr[idx].end(), v) - tr[idx].begin();
ll m = (s + e) / 2;
ll a = quelo(s, m, 2 * idx, qs, qe, v);
ll b = quelo(m + 1, e, 2 * idx + 1, qs, qe, v);
return a + b;
}
ll quehi(ll s, ll e, ll idx, ll qs, ll qe, ll v)
{
if (qs > e || qe < s || qs > qe)
return 0;
if (qs <= s && qe >= e)
return e - s + 1 - (upper_bound(tr[idx].begin(), tr[idx].end(), v) - tr[idx].begin());
ll m = (s + e) / 2;
ll a = quehi(s, m, 2 * idx, qs, qe, v);
ll b = quehi(m + 1, e, 2 * idx + 1, qs, qe, v);
return a + b;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, m; cin >> n >> m;
for (ll i = 0; i < n; i++)
cin >> ar[i];
build(0, n - 1, 1);
ll ansF = 0;
for (ll i = 0; i < n; i++)
ansF += quehi(0, n - 1, 1, 0, i, ar[i]);
while (m--)
{
ll ans = ansF;
ll L, R; cin >> L >> R; L--; R--;
ll a = quelo(0, n - 1, 1, L + 1, R - 1, ar[L]); ans -= a;
ll b = quehi(0, n - 1, 1, L + 1, R - 1, ar[L]); ans += b;
ll c = quehi(0, n - 1, 1, L + 1, R - 1, ar[R]); ans -= c;
ll d = quelo(0, n - 1, 1, L + 1, R - 1, ar[R]); ans += d;
if (ar[L] < ar[R])
ans++;
else if (ar[L] > ar[R])
ans--;
cout << ans << endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBzeiAyMDAxMDAKCnZlY3RvcjxsbD50cls0ICogc3pdOwpsbCBhcltzel07Cgp2b2lkIGJ1aWxkKGxsIHMsIGxsIGUsIGxsIGlkeCkKewoJaWYgKHMgPT0gZSkKCXsKCQl0cltpZHhdLnB1c2hfYmFjayhhcltzXSk7CgkJcmV0dXJuOwoJfQoJbGwgbSA9IChzICsgZSkgLyAyOwoJYnVpbGQocywgbSwgMiAqIGlkeCk7CglidWlsZChtICsgMSwgZSwgMiAqIGlkeCArIDEpOwoJbWVyZ2UodHJbMiAqIGlkeF0uYmVnaW4oKSwgdHJbMiAqIGlkeF0uZW5kKCksCgkgICAgICB0clsyICogaWR4ICsgMV0uYmVnaW4oKSwgdHJbMiAqIGlkeCArIDFdLmVuZCgpLAoJICAgICAgYmFja19pbnNlcnRlcih0cltpZHhdKSk7Cn0KCmxsIHF1ZWxvKGxsIHMsIGxsIGUsIGxsIGlkeCwgbGwgcXMsIGxsIHFlLCBsbCB2KQp7CglpZiAocXMgPiBlIHx8IHFlIDwgcyB8fCBxcyA+IHFlKQoJCXJldHVybiAwOwoJaWYgKHFzIDw9IHMgJiYgcWUgPj0gZSkKCQlyZXR1cm4gbG93ZXJfYm91bmQodHJbaWR4XS5iZWdpbigpLCB0cltpZHhdLmVuZCgpLCB2KSAtIHRyW2lkeF0uYmVnaW4oKTsKCWxsIG0gPSAocyArIGUpIC8gMjsKCWxsIGEgPSBxdWVsbyhzLCBtLCAyICogaWR4LCBxcywgcWUsIHYpOwoJbGwgYiA9IHF1ZWxvKG0gKyAxLCBlLCAyICogaWR4ICsgMSwgcXMsIHFlLCB2KTsKCXJldHVybiBhICsgYjsKfQoKbGwgcXVlaGkobGwgcywgbGwgZSwgbGwgaWR4LCBsbCBxcywgbGwgcWUsIGxsIHYpCnsKCWlmIChxcyA+IGUgfHwgcWUgPCBzIHx8IHFzID4gcWUpCgkJcmV0dXJuIDA7CglpZiAocXMgPD0gcyAmJiBxZSA+PSBlKQoJCXJldHVybiBlIC0gcyArIDEgLSAodXBwZXJfYm91bmQodHJbaWR4XS5iZWdpbigpLCB0cltpZHhdLmVuZCgpLCB2KSAtIHRyW2lkeF0uYmVnaW4oKSk7CglsbCBtID0gKHMgKyBlKSAvIDI7CglsbCBhID0gcXVlaGkocywgbSwgMiAqIGlkeCwgcXMsIHFlLCB2KTsKCWxsIGIgPSBxdWVoaShtICsgMSwgZSwgMiAqIGlkeCArIDEsIHFzLCBxZSwgdik7CglyZXR1cm4gYSArIGI7Cn0KCmludCBtYWluKCkKewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKDApOyBjb3V0LnRpZSgwKTsKCWxsIG4sIG07IGNpbiA+PiBuID4+IG07Cglmb3IgKGxsIGkgPSAwOyBpIDwgbjsgaSsrKQoJCWNpbiA+PiBhcltpXTsKCWJ1aWxkKDAsIG4gLSAxLCAxKTsKCWxsIGFuc0YgPSAwOwoJZm9yIChsbCBpID0gMDsgaSA8IG47IGkrKykKCQlhbnNGICs9IHF1ZWhpKDAsIG4gLSAxLCAxLCAwLCBpLCBhcltpXSk7Cgl3aGlsZSAobS0tKQoJewoJCWxsIGFucyA9IGFuc0Y7CgkJbGwgTCwgUjsgY2luID4+IEwgPj4gUjsgTC0tOyBSLS07CgkJbGwgYSA9IHF1ZWxvKDAsIG4gLSAxLCAxLCBMICsgMSwgUiAtIDEsIGFyW0xdKTsgYW5zIC09IGE7CgkJbGwgYiA9IHF1ZWhpKDAsIG4gLSAxLCAxLCBMICsgMSwgUiAtIDEsIGFyW0xdKTsgYW5zICs9IGI7CgkJbGwgYyA9IHF1ZWhpKDAsIG4gLSAxLCAxLCBMICsgMSwgUiAtIDEsIGFyW1JdKTsgYW5zIC09IGM7CgkJbGwgZCA9IHF1ZWxvKDAsIG4gLSAxLCAxLCBMICsgMSwgUiAtIDEsIGFyW1JdKTsgYW5zICs9IGQ7CgkJaWYgKGFyW0xdIDwgYXJbUl0pCgkJCWFucysrOwoJCWVsc2UgaWYgKGFyW0xdID4gYXJbUl0pCgkJCWFucy0tOwoJCWNvdXQgPDwgYW5zIDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==