#include <functional>
#include <algorithm>
#include <iostream>
#include <climits>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
#include <unistd.h>

using namespace std;

typedef long long        LL;
typedef pair<int, int>   pii;
typedef pair<int, pii>   piii;
typedef vector<int>      vi;
typedef vector<pii>      vii;
typedef vector<piii>     viii;

#ifdef _WIN32
#define getchar_unlocked getchar
#endif
inline void inpint( int &n ) {
  n=0; register int ch = getchar_unlocked(); bool sign = 0;
  while(ch < 48 || ch > 57) { if(ch == '-') sign = 1; ch = getchar_unlocked(); }
  while(ch >= 48 && ch <= 57) { n = (n << 3) + (n << 1) + ch - 48, ch = getchar_unlocked(); }
  if(sign) n = -n;
}

inline int sqr(int x){return x * x;}
inline int cube(int x){return x * x * x;}
inline LL sqrLL(LL x){return x * x;}
inline LL cubeLL(LL x){return x * x * x;}

const LL LLINF      = 9223372036854775807LL;
const LL LLINF17    = 100000000000000000LL;
const int INF       = 2147483647;
const int INF9      = 1000000000;
const int MOD       = 1000000007;
const double eps    = 1e-7;
const double PI     = acos(-1.0);

#define FOR(a,b,c)   for (int (a)=(b); (a)<(c); (a)++)
#define FORN(a,b,c)  for (int (a)=(b); (a)<=(c); (a)++)
#define FORD(a,b,c)  for (int (a)=(b); (a)>=(c); (a)--)
#define REP(i,n)     FOR(i,0,n)
#define REPN(i,n)    FORN(i,1,n)
#define REPD(i,n)    FORD(i,n,1)

#define RESET(a,b)   memset(a,b,sizeof(a))
#define SYNC         ios_base::sync_with_stdio(0);
#define SIZE(a)      (int)(a.size())
#define MIN(a,b)     (a) = min((a),(b))
#define MAX(a,b)     (a) = max((a),(b))
#define ALL(a)       a.begin(),a.end()
#define RALL(a)      a.rbegin(),a.rend()
#define SIZE(a)      (int)(a.size())
#define LEN(a)       (int)(a.length())

#define fi           first
#define se           second
#define pb           push_back
#define mp           make_pair
class FastInput {
  public:
    FastInput() {
      m_dataOffset = 0;
      m_dataSize = 0;
      m_v = 0x80000000;
    }
    inline uint32_t ReadNext() {
      if (m_dataOffset == m_dataSize) {
        int r = read(0, m_buffer, sizeof(m_buffer));
        if (r <= 0) return m_v;
        m_dataOffset = 0;
        m_dataSize = 0;
        int i = 0;
        if (m_buffer[0] < '0') {
          if (m_v != 0x80000000) {
            m_data[m_dataSize++] = m_v;
            m_v = 0x80000000;
          }
          for (; (i < r) && (m_buffer[i] < '0'); ++i);
        }
        for (; i < r;) {
          if (m_buffer[i] >= '0') {
            m_v = m_v * 10 + m_buffer[i] - 48;
            ++i;
          } else {
            m_data[m_dataSize++] = m_v;
            m_v = 0x80000000;
            for (i = i + 1; (i < r) && (m_buffer[i] < '0'); ++i);
          }
        }
      }
      return m_data[m_dataOffset++];
    }
  public:
    uint8_t m_buffer[32768];
    uint32_t m_data[16384];
    size_t m_dataOffset, m_dataSize;
    uint32_t m_v;
};

int n, m, arr[200005], root, bit[200005], compress[200005], compress1[200005], bitmax;
piii queries[200005];
LL ans[200005], inversions, tot;
int l = 0, r = 0;
inline bool cf(piii a, piii b){
	int lo = a.se.fi / root, hi = b.se.fi / root;
	if(lo != hi) return lo < hi;
	return a.se.se < b.se.se;
}
inline void update(int pos, int val){
	for(int i = pos; i <= bitmax; i += i & -i) bit[i] += val;
}
inline int query(int pos){
	int ret = 0;
	for(int i = pos; i; i ^= i & -i) ret += bit[i];
	return ret;
}
inline int queryBIT(int lo, int hi){
	int ret1 = (hi == bitmax) ? (r - l + 1) : query(hi);
	int ret2 = (lo == 1) ? 0 : query(lo - 1);
	return ret1 - ret2;
}
FastInput FI;
inline void go(){
	sort(compress+1,compress+1+n);
	int prev = -1;
	for(int i = 1; i <= n; i++){
		if(compress[i] != prev){
			++bitmax;
			compress1[bitmax] = compress[i];
			prev = compress[i];
		}
	}
}
int main(){
	n = FI.ReadNext(); m = FI.ReadNext();
	for(int i = 1; i <= n; i++){
		arr[i] = FI.ReadNext();
		compress[i] = arr[i];
	}
	go();
	for(int i = n; i >= 1; i--){
		arr[i] = lower_bound(compress1+1,compress1+1+bitmax,arr[i]) - compress1;
		inversions += query(arr[i]-1);
		update(arr[i],1);
	}
	for(int i = 1; i <= bitmax; i++) bit[i] = 0;

	for(int i = 1; i <= m; i++){
		queries[i].se.fi = FI.ReadNext();
		queries[i].se.se = FI.ReadNext();
		if(queries[i].se.fi > queries[i].se.se) swap(queries[i].se.fi, queries[i].se.se);
		queries[i].fi = i;
	}

	root = (int)sqrt(n*1.0);
	sort(queries+1,queries+1+m,cf);

	for(int i = 1; i <= m; i++){
		int nowl = queries[i].se.fi, nowr = queries[i].se.se;

		tot = inversions + (arr[nowr] > arr[nowl]) - (arr[nowl] > arr[nowr]);
		if(nowl == nowr){
			ans[queries[i].fi] = inversions;
		}
		else if(nowl == nowr - 1){
			ans[queries[i].fi] = tot;
		}
		else{
			int tmpl = nowl + 1, tmpr = nowr - 1;

			while(r < tmpr){
				r++;
				if(r) update(arr[r],1);
			}
			while(l > tmpl){
				l--;
				if(l) update(arr[l],1);
			}
			while(r > tmpr){
				if(r) update(arr[r],-1);
				r--;
			}
			while(l < tmpl){
				if(l) update(arr[l],-1);
				l++;
			}

			ans[queries[i].fi] = tot - queryBIT(1, arr[nowl] - 1) + queryBIT(arr[nowl] + 1, bitmax)
				+ queryBIT(1, arr[nowr] - 1) - queryBIT(arr[nowr] + 1, bitmax);
		}
	}

	for(int i = 1; i <= m; i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}