K. Kindergarten Problem
time limit per test
3 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

As a student in Taiwan, you might have experienced situations like these:

  • When you were in kindergarten, you asked a question, but your teacher said, "You'll learn that in elementary school."
  • When you got to elementary school and asked the same question again, your teacher replied, "You'll learn that in junior high."
  • When you finally reached junior high, you still hadn't forgotten the question that had been bothering you all this time. But your teacher said, "That's not part of the Comprehensive Assessment Program. You'll learn it if you get into a top senior high school."
  • Once you entered senior high school, you already knew what was coming. Your teacher said, "That's something you'll study in university."
  • Then you got into NTU, thinking you'd finally get your answer. But your professor said, "Come on! You learned that back in kindergarten."

That's when you realized the problem: you went to the wrong kindergarten.

To prevent others from making the same mistake, you decided to start your own kindergarten, where teachers are committed to giving students the best education possible, and always do their best to answer every question.

In the playground of your kindergarten, there are $$$N$$$ pillars lined up from left to right, numbered $$$1$$$ through $$$N$$$. The $$$i$$$-th pillar has height $$$h_i$$$, and all pillars have distinct heights. Thanks to your education system, your students are not only full of knowledge, but also physically strong. Their favorite game is jumping between pillars.

For any two pillars $$$i$$$ and $$$j$$$, if every pillar between them is shorter than both $$$i$$$ and $$$j$$$, then a student can jump between $$$i$$$ and $$$j$$$ in one move, in either direction.

The students have invented many game rules, but the most popular one goes like this: the jury announces two pillars, $$$s$$$ and $$$t$$$, and participants must reach $$$t$$$ starting from $$$s$$$ using valid jumps. There's one special rule: players can only move in the direction from $$$s$$$ to $$$t$$$. That is, if $$$s \lt t$$$, a student can only jump to pillars with larger indices than their current position; if $$$s \gt t$$$, only to pillars with smaller indices.

Let $$$f(s, t)$$$ denote the minimum number of moves required to reach $$$t$$$ from $$$s$$$ under these rules.

This morning, the kids want to select a range of pillars with consecutive indices as their new competition arena. They define the quality of an interval $$$[\ell, r]$$$ as:

$$$$$$ \sum_{\ell \leq s \lt t \leq r} f(s, t) $$$$$$

They have $$$Q$$$ candidate intervals, but they don't know how to compute the quality efficiently, so they're asking for your help.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$, representing the number of pillars and the number of candidate intervals, respectively.

The second line contains $$$N$$$ integers $$$h_1, h_2, \dots, h_N$$$, where $$$h_i$$$ denotes the height of the $$$i$$$-th pillar.

Each of the next $$$Q$$$ lines contains two integers $$$\ell_i$$$ and $$$r_i$$$, indicating that the $$$i$$$-th candidate interval is $$$[\ell_i, r_i]$$$.

  • $$$2 \leq N \leq 5 \cdot 10^5$$$
  • $$$1 \leq Q \leq 5 \cdot 10^5$$$
  • $$$1 \leq h_i \leq N$$$
  • $$$h_i \neq h_j$$$ for all $$$i \neq j$$$
  • $$$1 \leq \ell_i \lt r_i \leq N$$$
Output

Output $$$Q$$$ lines. On the $$$i$$$-th line, output a single integer representing the quality of the $$$i$$$-th candidate interval.

Example
Input
10 5
4 5 1 3 2 10 8 9 6 7
1 10
2 5
3 8
9 10
5 6
Output
95
8
25
1
1