회의 장소

KOI 마을에는 수직선 위에 $N$개의 집이 지어져 있다. 각 집에는 사람이 한 명씩 살고 있다. 사람이 사는 집의 좌표를 작은 순서대로 나열했을 때, $i$ ($1 \le i \le N$)번째 집의 좌표는 $X_i$ ($X_i > 0$)이다. 마을에 일이 생기면 마을 사람들은 회의 세트를 열어 일을 해결한다. 회의 세트에는 마을 사람 전체가 참여할 수도 있고, 일부만 참여할 수도 있다. 회의 세트는 여러 회의로 구성된다. 회의는 회의 세트의 모든 참여자가 그중 한 사람의 집에 모이는 방식으로 진행된다. 회의 세트에서는 참여자의 집마다 회의를 한 번씩 연다. 즉 $K$명이 회의 세트에 참여하면 회의는 $K$번 열린다.

회의 한 번에 드는 비용은 회의에 참여하는 각 사람이 자신의 집에서 회의 장소인 집까지 이동하는 거리의 합이다. 회의 세트의 피로도는 회의마다 모이는 집의 순서에 따라 달라진다. 회의 세트의 피로도는 모이는 순서에서 인접한 두 회의의 비용 차이의 합으로 정의한다.

예를 들어 좌표가 1, 3, 10, 11, 15인 곳에 집이 있고, 3, 10, 11번 집에 사는 사람들이 회의 세트에 참여한다고 하자. 좌표 3인 집에 모이는 비용은 $|3 - 3| + |3 - 10| + |3 - 11| = 15$이다. 좌표 10인 집에 모이는 비용은 $|10 - 3| + |10 - 10| + |10 - 11| = 8$이고, 좌표 11인 집에 모이는 비용은 $|11 - 3| + |11 - 10| + |11 - 11| = 9$이다. 모이는 집의 순서가 $3 - 10 - 11$이면 피로도는 $|15 - 8| + |8 - 9| = 8$이다. 순서가 $3 - 11 - 10$이면 피로도는 $|15 - 9| + |9 - 8| = 7$이다. 이 순서로 모일 때 피로도가 최소이다.

회의 세트에 참여하는 사람이 1명 이하이면 피로도는 $0$이다.

KOI 마을에서는 총 $Q$번 회의 세트가 열린다. $i$번째 회의 세트에는 집의 좌표가 $L_i$ 이상 $R_i$ 이하인 집에 사는 사람들이 참여한다. 각 회의 세트의 최소 피로도를 구하는 프로그램을 작성하라.

첫 번째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에는 집의 좌표 $X_i$가 증가하는 순서대로 주어진다.

다음 $Q$개의 줄에 회의 세트 정보가 주어진다. $i$ ($1 \le i \le Q$)번째 줄에는 $i$번째 회의 세트의 $L_i$와 $R_i$가 공백으로 구분되어 주어진다.

$Q$개의 줄을 출력한다. $i$ ($1 \le i \le Q$)번째 줄에는 $i$번째 회의 세트의 최소 피로도를 출력한다.

• 주어지는 모든 수는 정수이다.
• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $1 \le X_i \le 10^9$ ($1 \le i \le N$)
• $X_i < X_{i+1}$ ($1 \le i < N$)
• $1 \le L_i \le R_i \le 10^9$ ($1 \le i \le Q$)