Mô tả bài toán: Tối thiểu hóa số phép tăng để dãy con tăng dần

Bạn được cung cấp một mảng gồm ~n~ số nguyên. Bạn có thể thay đổi mảng bằng cách thực hiện các phép tăng giá trị của một phần tử bất kỳ lên một đơn vị.

Nhiệm vụ của bạn là xử lý ~q~ truy vấn. Với mỗi truy vấn, bạn cần xác định số phép tăng tối thiểu cần thực hiện để đoạn dãy con ~[a, b]~ trở thành một dãy tăng dần.

Một dãy tăng dần khi mọi phần tử thoả mãn: ~ x[i] \leq x[i + 1] ~

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~: kích thước mảng và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~: các phần tử của mảng.
• Sau đó có ~q~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~, mô tả một truy vấn:
  • ~a~: chỉ số bắt đầu (1-based index).
  • ~b~: chỉ số kết thúc (1-based index).

Output:

• Với mỗi truy vấn, in ra số phép tăng tối thiểu cần thực hiện để dãy con ~[a, b]~ tăng dần.

Ràng buộc:

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq x_i \leq 10^9~
• ~1 \leq a \leq b \leq n~

Ví dụ:

Input:

5 3
2 10 4 2 5
3 5
2 2
1 4

Output:

2
0
14

Giải thích:

1. Truy vấn ~[3, 5]~:

   • Đoạn là [4, 2, 5].
   • Chi phí:
     • ~4 \to 2~: không cần tăng.
     • ~2 \to 5~: cần tăng 3 đơn vị.
   • Tổng chi phí: ~3~.

2. Truy vấn ~[2, 2]~:

   • Đoạn chỉ có một phần tử [10], không cần tăng.
   • Tổng chi phí: ~0~.

3. Truy vấn ~[1, 4]~:

   • Đoạn là [2, 10, 4, 2].
   • Chi phí:
     • ~2 \to 10~: cần tăng 8 đơn vị.
     • ~10 \to 4~: không cần tăng.
     • ~4 \to 2~: không cần tăng.
   • Tổng chi phí: ~8 + 0 + 0 = 8~.