Close Numbers

It is generally known that Mr. Malnar is a member of Mensa, an international organization you can join only with a score on a standardized IQ test better than 98% of the population. Perhaps less known is that Mr. Malnar is also a member of Menza, an international organization you can join only if the annual count of standard restaurant portions you eat is higher than 98% of the population. On one occasion Mr. Malnar himself got confused and presented his Mensa membership card when entering Menza. The news spread quickly through the halls of Menza, so some curious members decided to test Mr. Malnar's cognitive abilities after the next group meal.

The curious members gathered empty plates and made n stacks from them: the first stack consisted of one plate, the second of two, and so on up to the n-th stack, which consisted of n plates. Then they shuffled those stacks, and Mr. Malnar had to answer q rapid-fire questions. Every question had the same form: "What is the smallest difference in the number of plates between some two stacks located between the l-th and r-th stack?" Formally, let the number of plates in the i-th stack be pi; then Mr. Malnar must determine

minl≤i<j≤r|pi - pj|

Interestingly, Mr. Malnar answered all questions within two seconds and used no more than 512 MiB of memory. You certainly cannot do that, but perhaps you could write such a program.

The first line contains the positive integers n and q from the problem statement. (1 ≤ n, q ≤ 3 · 104)

The second line contains the permutation p of length n from the problem statement.

The next q lines contain two positive integers l and r each. (1 ≤ l < r ≤ n)

In the i-th line, print the answer to the i-th query from the input.