정수 수열 $x_1,x_2,\ldots,x_n$이 주어진다. 정점의 번호가 $1$부터 $n$까지인 $n$개의 정점으로 이루어진 가중치 무방향 그래프 $G$를 생각하자. $u<v$인 모든 정점 쌍 $u,v$에 대해, 이 그래프에는 가중치가 $x_v-x_u$인 간선 $\{u,v\}$가 있다.

$x$는 반드시 정렬되어 있는 것은 아니므로 간선의 가중치는 음수일 수도 있다.

$\ell\le r$인 쌍 $(\ell,r)$에 대해, $G[\ell,r]$는 정점 $\ell,\ell+1,\ldots,r$이 유도하는 $G$의 부분 그래프를 나타낸다. 즉, 이 정점들로 이루어지며 양 끝점이 모두 이 범위에 있는 $G$의 간선을 정확히 모두 유지하는 그래프이다. $f(\ell,r)$를 $G[\ell,r]$의 스패닝 트리의 가능한 최소 총 가중치로 정의한다. 특히 $f(\ell,\ell)=0$이다.

$q$개의 쌍 $(\ell,r)$이 주어진다. 각 쌍에 대해 $f(\ell,r)$를 구하여라.

입력

첫째 줄에 두 정수 $n$과 $q$ ($1\le n,q\le2\cdot10^5$)가 주어진다. 각각 수열의 길이와 질의의 개수이다.

둘째 줄에 $n$개의 정수 $x_1,x_2,\ldots,x_n$ ($-10^9\le x_i\le10^9$)이 주어진다.

다음 $q$개의 줄에는 각각 하나의 질의를 나타내는 두 정수 $\ell$과 $r$ ($1\le\ell\le r\le n$)이 주어진다.

출력

$q$개의 줄을 출력하여라. $i$번째 줄에는 $i$번째 질의의 답을 나타내는 정수 하나를 출력해야 한다.

예제

입력 1

3 4
0 10 0
1 3
1 2
2 3
2 2

출력 1

-10
10
-10
0

참고

첫 번째 질의에서 세 간선의 가중치는 $10$, $0$, $-10$이다. 가중치가 $0$과 $-10$인 간선을 선택하면 총 가중치가 $-10$인 스패닝 트리를 얻는다.

두 번째와 세 번째 질의에는 정점이 두 개 있으므로, 각각의 답은 유일한 간선의 가중치인 $10$과 $-10$이다. 마지막 질의에는 정점이 하나 있으므로 답은 $0$이다.