C国有 n 座城市，编号是 1 到 n ，编号为 i 的城市有路到编号为 i+1 的城市（编号为 n 的城市没有路到其他的城市）。 C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。 商人阿龙再次来到C国旅游。他还是想贩卖水晶赚取旅费，在某个城市买入，再另一个城市卖出。 他将从编号为 a 的城市到编号到 b 的城市。请你帮他算算，最多能赚多少钱。 注：他最多进行一次买入和一次卖出。

输入描述:

第一行两个整数n和m，表示n个城市和m个询问。第二行n个整数，表示n座城市水晶的买入和卖出的价格。接下来m行，每行两个整数a,b，表示阿龙要从编号为a的城市到编号为b的城市（保证ab）。

输出描述:

对于每个询问输出阿龙最多能赚多少钱。

备注:

，价格不超过。