#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "queue"
#include "vector"
#include "queue"
#include "stack"
#include "ctime"
#include "set"
#include "map"
#include "cmath"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 2e5 + 10;
int n , m;

const ll M = 1e18;

struct tcurts {
	ll mx , smx , mn , smn , as1 , as2 , mxs , mns;
	int len;
	tcurts operator + ( tcurts S ) {
		tcurts ret;
		ret.len = S.len + len;
		ret.as2 = max( { as2 , S.as2 , mx + smx - S.mn - S.smn , as1 + S.as1 , mxs - S.mn , mx + S.mns } );
		
		ret.mxs = max( { mxs , S.mxs , as1 + S.mx , mx + S.as1 } );
		if( S.len > 1 ) ret.mxs = max( ret.mxs , mx - S.mn + S.mx );
		ret.mxs = max( ret.mxs , mx - S.mn + smx );
		
		ret.mns = max( { mns , S.mns , as1 - S.mn , - mn + S.as1 } );
		if( len > 1 ) ret.mns = max( ret.mns , mx - S.mn - mn );
		ret.mns = max( ret.mns , mx - S.mn - S.smn );
		
		ret.as1 = max( { as1 , S.as1 , mx - S.mn } );
		
		ret.mx = mx , ret.smx = smx;
		if( S.mx > ret.mx ) ret.smx = ret.mx , ret.mx = S.mx;
		else if( S.mx > ret.smx ) ret.smx = S.mx;
		if( S.smx > ret.smx ) ret.smx = S.smx;
		ret.mn = mn , ret.smn = smn;
		if( S.mn < ret.mn ) ret.smn = ret.mn , ret.mn = S.mn;
		else if( S.mn < ret.smn ) ret.smn = S.mn;
		if( S.smn < ret.smn ) ret.smn = S.smn;
		return ret;
	}
} T[MAXN << 2] ;


ll A[MAXN];
void build( int rt , int l , int r ) {
	if( l == r ) {
		T[rt] = ( tcurts ) { A[l] , -M , A[l] , M , -M , -M , -M , -M , 1 };
		return;
	}
	int m = l + r >> 1;
	build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
	T[rt] = T[rt << 1] + T[rt << 1 | 1];
//	cout << T[2].mxs << endl;
}
tcurts que( int rt , int l , int r , int L , int R ) {
	if( L <= l && R >= r ) return T[rt];
	int m = l + r >> 1;
	tcurts re = ( tcurts ) { -418254373 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 };
	if( L <= m ) re = que( rt << 1 , l , m , L , R );
	if( R > m ) {
		if( re.mx == -418254373 ) re = que( rt << 1 | 1 , m + 1 , r , L , R );
		else re = re + que( rt << 1 | 1 , m + 1 , r , L , R );
	}
	return re;
}

void solve() {
	cin >> n >> m;
	rep( i , 1 , n ) scanf("%lld",A + i) , A[i] = A[i] * A[i];
	build( 1 , 1 , n );
//	cout << T[2].as1 << ' ' << T[2].mxs << endl;
	rep( i , 1 , m ) {
		int l , r;
		scanf("%d%d",&l,&r);
		tcurts re = que( 1 , 1 , n , l , r );
		printf("%lld\n",re.as2);
	}
}

signed main() {
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}