Truy vấn Mảng Tăng dần

Cho mảng $n$ số nguyên $x_1,x_2,\dots ,x_n$. Với mỗi truy vấn cho đoạn $[a,b]$, hãy tính số phép tăng tối thiểu (mỗi phép tăng một phần tử lên 1) để đoạn con $x_a,x_{a+1},\dots ,x_b$ trở thành không giảm (tức $x_i\le x_{i+1}$ với mọi $i$).

Dữ liệu vào

• Dòng 1: Hai số nguyên $n$ và $q$ ($1\le n,q\le 2\times {10}^5$).
• Dòng 2: $n$ số nguyên $x_1,x_2,\dots ,x_n$ ($1\le x_i\le {10}^9$).
• $q$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $a$ và $b$ ($1\le a\le b\le n$).

Dữ liệu ra

Với mỗi truy vấn, in ra số phép tăng tối thiểu trên một dòng.

Ràng buộc

• $1\le n,q\le 2\times {10}^5$
• $1\le x_i\le {10}^9$
• $1\le a\le b\le n$

Ví dụ

Ghi chú

Để đoạn $[a,b]$ không giảm với chi phí nhỏ nhất, ta chỉ được tăng (không giảm) phần tử. Phần tử thứ $i$ sau khi tối ưu bằng $max(x_a,x_{a+1},\dots ,x_i)$. Chi phí là ${\sum }_{i=a}^b(max(x_a,\dots ,x_i)-x_i)$.