Bạn được cho một dãy số ~H~ gồm ~N~ phần tử và ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~L,R\ (1\le L\le R\le N)~. Với mỗi truy vấn, xét dãy số ~A=\{H_L,H_{L+1},\dots,H_R\}~, nhiệm vụ của bạn là sắp xếp lại dãy số ~A~ theo thứ tự bất kỳ sao cho tổng chênh lệch của hai phần tử liên tiếp bất kỳ trong dãy là lớn nhất có thể. Hay nói cách khác, bạn cần tối đa hóa giá trị của ~S=\sum_{i=1}^{R-L}|A_i-A_{i+1}|~.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ tương ứng với số lượng phần tử trong dãy ~H~ và số lượng truy vấn (~1\le N,Q\le 4\times 10^5~).

Dòng thứ hai gồm ~N~ số nguyên dương ~H_1,H_2,\dots,H_N~ tương ứng với giá trị của các phần tử trong dãy ~H~ (~1\le H_i\le 10^9~).

Cuối cùng là ~Q~ dòng, mỗi dòng gồm hai số nguyên dương ~L,R~ mô tả các truy vấn (~1\le L\le R\le N~).

Output

Với mỗi truy vấn, in ra kết quả trên một dòng là tổng chênh lệch tối đa có thể đạt được.

Scoring

Sample Input 1

5 2
1 2 3 4 8
1 5
1 3

Sample Output 1

17
3