Description

数轴上有 $n$ 棵树，第 $i$ 棵树在位置 $i$ ，高度为 $a_i$

青蛙只能从位置为 $i$ 的树跳到位置为 $i+1$ 的树上。如果 $a_i \geq a_{i+1}$ ，那么青蛙不需要消耗任何体力，否则需要消耗 $a_{i+1} - a_{i}$ 的体力。

给定 $m$ 个询问，每个询问给出两个数 $l,r$ ，你需要求出青蛙从树 $l$ 依次跳到树 $l+1,l+2,\cdots,r-1,r$ 消耗的体力。

Input

第一行两个正整数 $n,m$ ，表示树的个数和询问次数4

接下来一行 $n$ 个正整数，表示数组 $a$

接下来 $m$ 行每行两个正整数 $l,r (l \leq r)$ ，表示一次询问

Output

对于每个询问输出一行答案

Limitation

对于 $40\%$ 的数据， $1 \leq n \leq 10000$

另有 $20\%$ 的数据，保证 $a_i \leq a_{i+1}$

对于 $100\%$ 的数据，保证 $1 \leq n \leq 1000000,1 \leq a_i \leq 10^9,1 \leq l \leq r \leq n$

Sample

5 5
8 8 9 6 4 
1 1
2 2
1 3
2 4
2 5

0
0
1
1
1