KOI 마을에는 N개의 집이 수직선 위에 지어져 있다. 각 집에는 사람들이 한 명씩 살고 있다.

사람들이 살고 있는 집의 좌표를 작은 순서대로 차례대로 나열했을 때, i (1 \le i \le N)번째 집의 좌표는 X_i (X_i \gt 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이하인 집에 사는 사람들이 참여한다.

각 회의 세트의 최소 피로도를 구하는 프로그램을 작성하라.

[제약 조건]

주어지는 모든 수는 정수이다.

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 \lt X_{i+1} (1 \le i \le N)

1 \le L_i \le R_i \le 10^9 (1 \le i \le Q)

#7018 upload 194회 done 45회 how_to_reg 34명 call_split 서브태스크

회의 장소 timer 3초 memory 1024MB

#7018
서브태스크

회의 장소 3초 1024MB