nocriz同学想要通过炒房投资。
nocriz
现有一长度为 nnn 的数列 aaa ，aia_iai 代表第 iii 天的房价.
现在有 qqq 次询问，每次给出 lll , rrr，代表nocriz同学在第 lll 天到第 rrr 天进行投资，就是说买房和卖房都在这些天的区间内。可以最多购买和售出一次，售出日期必须在购买日期之后。每次输出最大收益。
第一行两个整数 nnn , qqq。
第二行 nnn 个整数用一个空格隔开 a1,a2,…，ana_1,a_2, \ldots ， a_na1,a2,…，an。
接下来 qqq 行，每行两个整数 lll , rrr。
输出 qqq 行，每行一个整数，代表最大收益。
5 5 1 3 2 4 5 1 2 2 3 2 4 2 5 1 5
2 0 2 3 4
1≤n,q≤2⋅1051 \le n,q \le 2 \cdot 10^51≤n,q≤2⋅105
1≤ai≤1091 \le a_i \le 10^91≤ai≤109