601_B. Lipshitz Sequence_21726
A function <image> is called Lipschitz continuous if there is a real constant K such that the inequality |f(x) - f(y)| ≤ K·|x - y| holds for all <image>. We'll deal with a more... discrete version of this term.

For an array <image>, we define it's Lipschitz constant <image> as follows:

  * if n < 2, <image>
  * if n ≥ 2, <image> over all 1 ≤ i < j ≤ n



In other words, <image> is the smallest non-negative integer such that |h[i] - h[j]| ≤ L·|i - j| holds for all 1 ≤ i, j ≤ n.

You are given an array <image> of size n and q queries of the form [l, r]. For each query, consider the subarray <image>; determine the sum of Lipschitz constants of all subarrays of <image>.

Input

The first line of the input contains two space-separated integers n and q (2 ≤ n ≤ 100 000 and 1 ≤ q ≤ 100) — the number of elements in array <image> and the number of queries respectively.

The second line contains n space-separated integers <image> (<image>).

The following q lines describe queries. The i-th of those lines contains two space-separated integers li and ri (1 ≤ li < ri ≤ n).

Output

Print the answers to all queries in the order in which they are given in the input. For the i-th query, print one line containing a single integer — the sum of Lipschitz constants of all subarrays of <image>.

Examples

Input

10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9


Output

17
82
23
210


Input

7 6
5 7 7 4 6 6 2
1 2
2 3
2 6
1 7
4 7
3 5


Output

2
0
22
59
16
8

Note

In the first query of the first sample, the Lipschitz constants of subarrays of <image> with length at least 2 are:

  * <image>
  * <image>
  * <image>



The answer to the query is their sum.
import java.io.*;
import java.util.*;

/**
 * Created by slycer on 11/30/15.
 */
public class LipshitzSequence {

    public static void main ( String [] args ) throws IOException {

        BufferedReader reader = new BufferedReader ( new InputStreamReader( System.in ) );
        String [] aux = reader.readLine().split( " " );
        int n = Integer.valueOf( aux[0] );
        int m = Integer.valueOf( aux[1] );
        int [] data = new int[n];
        aux = reader.readLine().split( " " );
        for ( int i=0; i<n; i++ ){
            data[i] = Integer.valueOf( aux[i] );
        }
        int [] delta = new int[n-1];
        // delta[i] = (data[i+1]-data[i])/1

        for ( int i=0; i<n-1; i++ ){
            delta[i] = Math.abs( data[i+1] - data[i] );
        }

        Map<String,Long> sols = new HashMap<>();

        PrintWriter output = new PrintWriter( System.out );
        for ( int i=0; i<m; i++ ){
            aux = reader.readLine().split( " " );
            SumStack sum = new SumStack();
            int a = Integer.valueOf( aux[0] ) - 1;
            int b = Integer.valueOf( aux[1] ) - 1;

            String key = a + " " + b;

            if ( sols.get( key ) == null ){

                long sol = 0;
                for ( int j=a; j<b; j++ ){
                    sum.add( delta[j] );
                    sol += sum.sum;
                }
                sols.put( key, sol );
            }
            output.println( sols.get( key ) );
        }
        output.flush();;

    }

    static class Pair {
        long value;
        long count;
    }

    static class SumStack {
        long sum = 0;
        Stack<Pair> stack = new Stack<Pair>();

        public void add( int value ){
            Pair p = new Pair();
            p.value = value;
            p.count = 1;
            sum += value;
            while ( stack.size() > 0 && stack.peek().value <= p.value  ){
                Pair pop = stack.pop();
                sum -= pop.value * pop.count;
                sum += p.value * pop.count;
                p.count += pop.count;
            }
            stack.add( p );
        }
    }

   static class BinaryIndexedTree {

        long [] data;

        public BinaryIndexedTree( int n ){
            data = new long[n+1];
        }

        public void update( int index, int value ){
            while ( index < data.length ){
                data[ index ] += value;
                index = index + ( index & -index );
            }
        }

        // suma de la 1 pana la index
        public long sum( int index ){
            long ret = 0;
            while ( index > 0 ){
                ret += data[ index ];
                index = index - ( index & -index );
            }
            return ret;
        }

    }

}



