题目背景

翻译自 CSES-2416 题。

题目描述

给定一个包含 $n$ 个整数的数组。数组元素的索引从 $1$ 到 $n$。

你可以通过以下操作修改数组：选择一个数组元素，并将其值增加 $1$。

你的任务是处理 $q$ 个查询，每个查询的形式是：在考虑从位置 $a$ 到位置 $b$ 的子数组时，最少需要多少次操作才能使这个子数组变为递增的？

一个数组是递增的，当且仅当每个元素大于或等于前一个元素。

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示数组的大小和查询的数量。

第二行包含 $n$ 个整数 $x_1,x_2,…,x_n$：表示数组的值。

接下来有 $q$ 行，每行描述一个查询。每个查询包含两个整数 $a$ 和 $b$：表示查询区间子数组的起始和结束位置。

输出格式

对于每个查询，输出最少需要多少次操作使得该子数组变为递增的。

样例

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

2
0
14

说明/提示

$1 \leq n,q \leq 2 \cdot 10^5$；

$1 \leq x \leq 10^9$；

$1 \leq a \leq b \leq n$。