题目描述

达拉然国中有一条长为 $n$ 的街道，其中住了 $q$ 个法师,并且街道中每一户仅存在一种法力水晶 $a_i$ 。

法师们会一种神奇的法术，就是瞬间收集一个法力水晶，其需要消耗的法力值就是该法师到法力水晶的距离。

每个法师都喜欢一些法力水晶，并且喜欢的种类都恰好是一个连续的区间 $[l, r]$ 。

他想收集到街道中每一种他喜欢并且存在的法力水晶，每一种只需收集一个。

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

输入格式

第一行两个整数 $n, q$。
第二行共 $n$ 个整数,其中第 $i$ 个为 $a_i$ 。
接下来共 $q$ 行,每行三个整数 $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\le n, q \le 1000$ 。
另有 $10 \%$ 的数据满足 $a_i = i$ 。
另有 $30 \%$ 的数据满足 $\forall i, l_i =1, r_i = n$ 。
对于 $100 \%$ 的数据满足 $1\le n, q \le 2 \times 10^5$ ， $1\le l, r, p, a_i \le n$。