Simple Query Problem

Time limit3sMemory limit1024 MB

Summary

Given a permutation and range queries, compute the sum of |a_i - a_j| over all pairs i <= j inside each query range.

Level: Medium6 of 10
Topics: Array, Segment tree, Sorting
Solved: No attempts yet

Problem

You are given a permutation $a_1, a_2, \ldots, a_N$ of the numbers $1$ through $N$ . Write a program that processes the following query.

$l$ $r$ : Print the value of $\sum_{l \leq i \leq j \leq r}{|a_i - a_j|}$ .

Input

The first line contains $N$ and $Q$ , separated by a space. The second line contains the permutation of length $N$ , separated by spaces. Lines 3 through $Q+2$ each contain $l$ and $r$ , separated by a space, one query per line.

Output

Print the answer to each query on its own line.

Constraints

$1 \leq a_i \leq N$
$1 \leq l \leq r \leq N$

Examples1

Example 1
Input
```
4 2
4 1 3 2
1 3
2 4
```
Expected output
```
6
4
```