{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003e$N$ (1≤N≤50000) trees are lined up in a row. Given the height of each tree, $H$ (1≤H≤1000000), Xiao Ming was asked to answer $M$ (1≤M≤200000) questions. Each question contains two numbers $L$ and $R$ (1≤L≤R≤N), asking the height difference between the tallest tree and the shortest tree in interval [L,R]. Help Xiao Ming to solve the problem.\u003c/p\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eThe first line of the input contains two integers $N$($1$≤$N$≤$50000$) and $M$($1$≤$M$≤$200000$), denoting the number of trees and the number of questions.\n\u003cbr\u003eEach of the following $N$ lines contains one integer $Hi$, denoting the height of each tree.\u003cbr\u003eEach of the following $M$ lines contains two integers $Li$ and $Ri$, denoting the interval of each question.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eFrom the $1$st line to the $M$th line, each line contains one integer, which represents the height difference between the tallest tree and the shortest tree from the $L$th tree to the $R$th tree.\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e5 3\n5\n2\n9\n8\n1\n1 2\n1 4\n3 5\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3\n7\n8\u003c/pre\u003e"}},{"title":"I/O Description","value":{"format":"HTML","content":"In interval [1,2], the heights are 5,2. The height difference is 5-2\u003d3.\u003cbr\u003e\nIn interval [1,4], the heights are 5,2,9,8. The height difference is 9-2\u003d7.\u003cbr\u003e\nIn interval [3,5], the heights are 9,8,1. The height difference is 9-1\u003d8."}}]}