/*
 *     Date:
 *        2015/06/20
 *     Author:
 *        _Rover
 */
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, q, a[1234], l, r, dp[1234][1234], f[1234][1234];
int main(){
    //freopen( "" , "r" , stdin );
    //freopen( "" , "w" , stdout );
    while( scanf( "%d %d" , &n , &q ) != EOF ){
        for( int i = 1 ; i <= n ; i ++ )
            scanf( "%d" , &a[i] );
        memset( dp , 0 , sizeof( dp ) );
        memset( f , 0 , sizeof( f ) );
        for( int j = 1 ; j <= n ; j ++ )
            for( int i = j - 1 ; i ; i -- ){
                f[i][j] = f[i+1][j] + ( a[i] > a[j] );
                dp[i][j] += dp[i][j-1] + f[i][j];
            }
        while(q--){
            scanf("%d %d", &l, &r);
            printf("%d\n", dp[l][r] );
        }
        
    }
    return 0;
}