Dãy Lipschitz

Với một dãy số nguyên $a[1..m]$, ta định nghĩa hằng số Lipschitz $L(a)$ như sau:

• Nếu $m<2$ thì $L(a)=0$.
• Nếu $m\ge 2$ thì $L(a)$ là số nguyên không âm nhỏ nhất sao cho $|a[i]-a[j]|\le L(a)·|i-j|$ với mọi $1\le i,j\le m$.

Cho một dãy $h$ gồm $n$ phần tử và $q$ truy vấn dạng $[l,r]$. Với mỗi truy vấn, xét dãy con liên tiếp $h[l],h[l+1],\dots ,h[r]$; hãy tính tổng hằng số Lipschitz của tất cả các dãy con liên tiếp của dãy đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $h[1],h[2],\dots ,h[n]$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$ mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa một số nguyên là tổng hằng số Lipschitz của tất cả các dãy con liên tiếp của $h[l_i..r_i]$.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le q\le 100$
• $0\le h[i]\le {10}^8$
• $1\le l_i<r_i\le n$

Ví dụ