Counting Good Pairs in an Array

You are given an array of n integers: \(a_1, a_2, \dots, a_n\). A pair \((x,y)\) (with \(x \neq y\)) is considered a good pair if for every index \(i\) (\(i \neq x,\ 1 \le i \le n\)), the following inequality holds:

[ |a_x - a_y| \le |a_x - a_i| ]

In other words, for a fixed index \(x\), the element \(a_y\) is one of the closest values to \(a_x\) among all other elements. Note that the relation is not necessarily symmetric; that is, \((x,y)\) being good does not imply \((y,x)\) is good.

You will be given several queries. Each query is described by two integers \(l\) and \(r\). For each query, consider only the indices in the range \([l, r]\). Count how many ordered pairs \((x, y)\) (with \(x \neq y\) and \(l \le x,y \le r\)) form a good pair.

Note on Determining Good Pairs:

• If there exists at least one index \(y\) with \(a_y = a_x\) (and \(y \neq x\)), then the minimum possible difference is \(0\) and every other index with the same value as \(a_x\) qualifies.
• If \(a_x\) is unique, let \(d = \min\{ |a_x - v| : v \text{ is a value that appears in the array and } v \neq a_x \}\). Then every index \(y\) with \(|a_x - a_y| = d\) qualifies.

inputFormat

The first line contains two integers \(n\) and \(q\) representing the number of elements in the array and the number of queries, respectively.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

Each of the next \(q\) lines contains two integers \(l\) and \(r\) representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of good ordered pairs \((x,y)\) (with \(x \neq y\)) such that \(l \le x,y \le r\).

sample

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

8
4
2