3236. 马猴烧酒

【题目描述】

众所周知，NTZ是一个马猴烧酒。机房里有一个长为n的过道，过道一旁有n个电脑，并且每一个电脑仅存下载了一种游戏。

NTZ会一种神奇的法术，就是瞬间把一个电脑的游戏复制到自己面前的电脑上，其需要消耗的法力值就是NTZ到电脑的距离。

他在p位置，想玩到所有电脑中每一种他喜欢并且存在的游戏，每一种只需复制一个。并且喜欢的种类都恰好是一个连续的区间[l,r]

而NTZ很懒还很贪玩，NTZ会呆在他所在的位置不会走动，他想知道最少需要耗费多少法力值才能满足要求。

并且在你完成了一次计算后，他会把自己复制到另一个位置，形成一个喜好可能不同的NT小Z，再让你计算满足他的要求需要的法力值消耗。并且我们知道，他会复制(q-1)次。

【输入格式】

第一行两个整数n，q

第二行共n个整数，其中第i个为ai

第三行三个整数，为NTZ的p,l,r

接下来共(q-1)行，每行三个整数一次为每个分身的p,l,r

【输出格式】

共q行,每行一个整数,其中第i个为第i个马猴烧酒需要的花费的最小法力值。

【样例输入】

5 4
1 5 3 3 1
3 3 4
4 4 5
2 1 4
5 3 5

【样例输出】

0
2
2
4

【提示】

对于30%的数据满足1<=n,q<=1000。

另有10%的数据满足ai=i。

另有30%的数据满足，对于任意的i，li=1,ri=n。

对于100%的数据满足1<=n,q<=2e5,1<=l,r,p,ai<=n。

【来源】

LOJ

【样例解释】

刚开始NTZ在3处，喜欢的种类是[3,4],但由于4不存在，只需要找到3，他位置上刚好有一个为3的游戏，故最小消耗为0。

第一个NT小Z只需取a2=5，那么消耗为|2-4|=2。

第二个NT小Z取最近的两个即可，取a1=1，a3=3，消耗为|1-2|+|3-2|=2。

第三个NT小Z取a4=3，a2=5，消耗为|4-5|+|2-5|=4。