题目描述

小明参加了2021年的noip得了一等奖，他对T3 方差这道题印象非常深刻（饱受折磨）。

题目大概：任选序列里的i，可将$a_i$​​ 变成$a_{i-1}+a_{i+1}-a_i$​​ ，在若干次操作后，使序列的方差变成最小。

风水轮流转，今年轮到小明出题了，他想着方差可以出题，那绝对差也可以啊，于是小明就出了以下的排列题。

对n个元素的序列{$a_i$}任意排列，使得相邻数之差的绝对值的总和最大。

然而小花审核这个题目觉得太简单了，于是小明最后改成了：

n个元素的序列{$a_i$}，m次询问，每次询问下标区间[L, R]，在区间[L, R]里做任意排列（不改变原序列），使得区间内相邻数之差的绝对值的总和最大。

输入输出格式

输入格式；

第一行n和m 第二行n个数，表示序列{$a_i$} 接下来m行，每行L、R，表示一个询问

输出格式：

m行，每行一个数字，表示询问的结果 如果L==R，就输出0

输入输出样例

5 3
1 5 8 3 9
1 3
2 4
2 5

11
8
15

样例1说明：

[1,3]的最佳排列5 1 8，答案是11 [2,4]的最佳排列5 8 3，答案是8 [2,5]的最佳排列5 9 3 8，答案是15

测试点

测试限制：每个测试点时间限制1s，内存限制128M。

数据范围：

• $20\%：n、m<=8$
• $40\%：n、m<=1000$
• $60\%：n、m<=5000$
• $100\%：$$n、m<=10^5$,$1<=a_i<=10^9$，$1<=x<=y<=n$