James is practicing his parkour skills at a local urban park. The park has ~N~ pillars of varying heights arranged in a line. James moves between these pillars by either performing a Hip, meaning he moves to an adjacent pillar; or a Hop, meaning he hops to the second pillar to his left or right.

James is practicing ~Q~ routes along these pillars. Each route consists of a start and end destination. James' biggest concern is the effect the elevation changes have on his knees, so he would like to minimize the sum of the differences in heights for each Hip and Hop he makes.

Input Specification

The input begins with two integers ~N, Q~ ~(1 \le N, Q \le 300,000)~. The next line contains ~N~ integers ~H_i~ ~(1 \le H_i \le 10^9)~, the height of a pillar. The next ~Q~ lines each contain two integers ~S_i, F_i~ ~(1 \le S_i, F_i \le N)~, the start and finish pillar for each route.

For 30% of cases, ~Q = 1~.
For 60% of cases, ~N \le 10,000~.

Output Specification

For each route, output the minimum sum of the differences in heights for each Hip or Hop that James takes.

Sample Input 1

5 3
1 4 2 1 2
1 3
5 1
2 5

Sample Output 1

1
1
2