408088: GYM102984 D Non-Decreasing Subarray Game

Yuto and Platina are going to play a Non-Decreasing Subarray Game. The game is played on an array $$$A$$$ of length $$$N$$$.

Yuto first says an integer, and after that, Platina says an integer. The numbers selected by the players should be in the interval from $$$L$$$ to $$$R$$$, inclusive. Let the two selected integers be $$$a$$$ and $$$b$$$, ordered in such a way that $$$a \le b$$$. Then the score obtained in the game is the number of pairs $$$(i, j)$$$ such that $$$a \le i \le j \le b$$$ and the interval $$$[i, j]$$$ forms a non-decreasing subarray in array $$$A$$$.

We say that $$$[i, j]$$$ forms a non-decreasing subarray when, for each $$$x$$$ and $$$y$$$ such that $$$i \le x \le y \le j$$$, it is true that $$$A[x] \le A[y]$$$.

Yuto wants the score to be minimized, and Platina wants the score to be maximized. This game is so much fun that we are going to play it $$$T$$$ times. All games will use the same array $$$A$$$, but different games might use different values of $$$L$$$ and $$$R$$$.

Assuming that both players are playing optimally, find the number of points they will get in each of the games played.

The first line contains two integers $$$N$$$ and $$$T$$$ ($$$1 \le N, T \le 500\,000$$$): the length of the array and the number of games played, respectively.

In the second line, the array values $$$A[1]$$$, $$$A[2]$$$, $$$A[3]$$$, $$$\ldots$$$, $$$A[N]$$$ are given ($$$1 \le A[i] \le 10^9$$$).

Each of the next $$$T$$$ lines describes a game by two positive integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \le L_i \le R_i \le N$$$): the values of $$$L$$$ and $$$R$$$ to use for this game.

For each game, print the score in this game on a separate line.

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

4
1
4
7
3