题目描述

antant的蚂蚁工厂里生产的机器蚂蚁叛逃了！幸好，作为c语言膏手的antant成功的黑入了机器蚂蚁的集体意识网络，他现在需要控制机器蚂蚁们集合并销毁

将蚁穴视为数轴，总共有 n 只机器蚂蚁分布在蚁穴的各个位置 ，蚂蚁的编号为1 到 n , 编号为 i 的机械蚂蚁的坐标为 a_i，机械蚂蚁的位置各不相同

由于antant的技术有限，他每次只能操控编号为 [l,r] 的机械蚂蚁，令他们前往坐标 [K,K+r-l] 的区间内集合后销毁，同样，每只机械蚂蚁集合后的坐标也不能相同

机械蚂蚁从坐标 x 移动到坐标 y 需要花费 |y-x| 的能量，antant希望你帮他计算在已知 l,r,K 的情况下，机械蚂蚁所花费的最小能量总和是多少

输入格式

第一行输入两个整数 n,m 分别表示机械蚂蚁总数和指令的数量

第二行输入 n 个整数 a_i 分别表示每只机械蚂蚁的初始坐标

接下来的 m 行，每行包括三个整数 l,r,K 表示一条指令

注意：

1.指令之间相互独立，也就是说每条指令计算时所有蚂蚁均位于初始位置

2.如果发出指令时，有编号不属于 [l,r] 的蚂蚁位于 [K,K+r-l] 区间内，忽略它们，不需计算对应情况

输出格式

共 m 行，对于每一条指令，输出一个整数表示所花费的最小能量总和

输入样例

5 3   
1 5 7 6 2   
1 5 2   
1 3 9   
3 5 5

输出样例

5   
17  
3

数据范围

对于 30% 的数据，n,m <= 10

对于 50% 的数据，n,m <= 10^3

对于 100% 的数据，n,m <= 5 * 10^5 , 1 <= a_i,K <= 10^6