문제

Mr. Tzanca Hurricane wants to go visit his goddess girlfriend who lives on Mount Olympus. When planning his trip, he knows the temperature on the mountain for $n$ consecutive days. The temperature values can be viewed as an array $t$ of $n$ integers where $t_i$ represents the temperature on the $i$-th day.

Since the gasoline prices went up, he is very cautious with the gas consumption of his red Ferrari. In particular, he doesn't want to waste gas on cooling or heating. Mr. Hurricane doesn't want the temperature to be too low or too high. He has $q$ temperature ranges that he finds comfortable.

For each temperature range $(x, y)$ Mr. Hurricane gives you, he is curious how many different pairs $(\ell, r)$ there are such that $\min(t_{\ell}, t_{\ell + 1}, \ldots, t_{r}) = x$ and $\max(t_{\ell}, t_{\ell + 1}, \ldots, t_{r}) = y$. Please help him figure that out.

입력

The first line of input contains two integers $n$ and $q$ ($1 \leq n, q \leq 10^{5}$).

The second line contains $n$ integers $t_1, t_2, \ldots, t_n$ ($1 \leq t_i \leq n$).

The next $q$ lines describe the queries. The $i$-th of them contains the integers $x_i$ and $y_i$ ($1 \leq x_i \leq y_i \leq n$).

출력

The output will consist of $q$ lines, the $i$-th line containing a single integer, the answer to the $i$-th query.

제한

힌트