== include(page="template/taskheader" task_id="nrsubsecv") ==

Sandu the Great Thinker is known for the fact that he always asks himself philosophical questions. Today, having an array of $N$ elements, he desires to answer to $M$ queries of the following format: _Given $x$ and $y$, how many substrings (containing consecutive elements) of the array have the minimum element between $x$ and $y$?_.
You have to prove Sandu that you are as interested in philosophy as he is, and answer to his $M$ queries.

Sandu Marele Cugetător este cunoscut pentru faptul că tot timpul îşi pune foarte multe întrebări filosofice. Astăzi, având un şir de $N$ elemente, el doreşte să răspundă la $M$ întrebări de forma: _Fiind date un $x$ si $y$, câte subsecvenţe din şirul dat au elementul minim cuprins între $x$ si $y$?_.
Voi trebuie să îi arătaţi lui SMC că sunteţi la fel de preocupaţi de treburi filosofice ca şi el, şi să îi răspundeţi la cele $M$ întrebări.

h2. Input

h2. Date de intrare

The input file $nrsubsecv.in$ contains on its first line two natural numbers, $N$ and $M$, representing the number of elements in the array and the number of querries. The second line contains $N$ natural numbers, the elements of the array. Each of the next $M$ lines contains two natural numbers, $x$ and $y$, $x ≤ y$, as explained in the problem's statement.

Fişierul de intrare $nrsubsecv.in$ conţine pe prima linie două numere naturale $N$ si $M$, reprezentând numărul de elemente din şir, respectiv numărul de întrebări ale lui SMC. A doua linie conţine $N$ numere naturale, reprezentând elementele şirului. Următoarele $M$ linii conţin fiecare câte două numere naturale $x$ si $y$, $x ≤ y$, cu semnificaţia din enunţ.

h2. Output

h2. Date de ieşire

The output file $nrsubsecv.out$ should contain $M$ lines, the $i$-th one containing the answer to the $i$-th question in the input.

Fişierul de ieşire $nrsubsecv.out$ trebuie să conţină $M$ linii, pe a $i$-a linie aflându-se răspunsul la a $i$-a întrebare din fişierul de intrare.

h2. Restrictions

h2. Restricţii

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 100.000$

* All the elements in the array lie in the interval $[0, 10^6^]$

* Elementele şirului se află în intervalul $[0, 10^6^]$

* $0 ≤ x ≤ y ≤ 10^6^$

* *Attention!* Sandu recommends $64$ bit integer data types for computing the answer.

* *Atenţie!* SMC recomandă tipuri de date pe $64$ de biţi cu semn pentru afişarea răspunsului.

h2. Example

h2. Exemplu

table(example). |_. nrsubsecv.in |_. nrsubsecv.out |
|12 3

3
|

h3. Sample test explanation

h3. Explicaţie

The $37$ substring with the minimum equal to $2$ are: $[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [4, 9], [5, 6], [5, 7], [5, 8], [5, 9], [6, 6], [6, 7], [6, 8], [6, 9], [11, 12]$ şi $[12, 12]$.

Cele $37$ de subsecvente care au minimul $2$ sunt: $[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [4, 9], [5, 6], [5, 7], [5, 8], [5, 9], [6, 6], [6, 7], [6, 8], [6, 9], [11, 12]$ şi $[12, 12]$.

== include(page="template/taskfooter" task_id="nrsubsecv") ==
 

== include(page="template/taskfooter" task_id="nrsubsecv") ==