∑|ΔEasyMAX|

GUN, a composer, likes writing songs whose tempo changes.

After finishing a song with all his effort, GUN became curious about the total per-second tempo change of his song. But GUN's song has so many places where the tempo changes that computing the sum of changes over a range by hand is hard. GUN asks you to find the sum of per-second tempo changes over specific ranges of the song. Help GUN find the sum of per-second tempo changes for the given ranges.

The sum of per-second tempo changes between second i and second j is defined as $\sum_{k=i}^{j-1}|a_{k+1} - a_k|$, and when $j-1 < i$, $\sum_{k=i}^{j-1}|a_{k+1} - a_k| = 0$.

The symbol |a| denotes, for any real number a, |a| = -a if a<0 and |a| = a if a≥0.

The first line of the input gives N(1 ≤ N ≤ 1,000), the length in seconds of the song GUN wrote, and Q(1 ≤ Q ≤ 1,000), the number of ranges whose per-second tempo change sums must be computed, separated by a space.

The second line gives the sequence a1 a2, ... , an representing the tempo of GUN's song in order, separated by spaces, where ai(-104 ≤ ai ≤ 104) is the tempo at second i.

From the third line, Q lines follow, each giving the start and end points Q(i,l), Q(i,r) (1 ≤ Q(i,l) ≤ Q(i,r) ≤ N) of a range whose change sum must be computed.

For each range of GUN's song, output the sum of per-second tempo changes in input order over Q lines.