Description

Given $n$ numbers $a_1,\cdots,a_n$.

For a pair $(x,y)$, if for all $i=1,2,\cdots,n$, it satisfies $|a_x-a_y|\le|a_x-a_i|(i\not=x)$, then $(x,y)$ is called a good pair ($|x|$ denotes the absolute value of $x$).

You are given several queries. For each query, ask how many good pairs are contained in the interval $[l,r]$.

That is, choose $x,y$ ($l\le x,y\le r$ and $x\not=y$), and ask how many pairs $(x,y)$ are good pairs.

Input Format

The first line contains two positive integers $n,m$.

The second line contains $n$ numbers $a_1,\cdots,a_n$.

In the next $m$ lines, each line gives two numbers $l,r$.

Output Format

Let $Ans_i$ be the answer to the $i$-th query. Output $\sum_{i=1}^m\limits Ans_i\times i$.

3 2
2 1 3
1 2
1 3

10

Hint

Sample Explanation

In the first query, the good pairs are: $(1,2)(2,1)$.

In the second query, the good pairs are: $(1,2)(2,1),(1,3)(3,1)$.

The answer $=2\times 1+4\times 2=10$.

Constraints

Translated by ChatGPT 5