Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | nrsubsecv.in, nrsubsecv.out | Sursă | Infoarena Cup 2012 |
| Autor | Andrei Parvu | Adăugată de |  Cezar Mocan •CezarMocan |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
Input
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.
Output
The output file nrsubsecv.out should contain M lines, the i-th one containing the answer to the i-th question in the input.
Restrictions
- 1 ≤ N ≤ 1.000.000
- 1 ≤ M ≤ 100.000
- All the elements in the array lie in the interval [0, 106]
- 0 ≤ x ≤ y ≤ 106
- Attention! Sandu recommends 64 bit integer data types for computing the answer.
Example
| nrsubsecv.in | nrsubsecv.out |
|---|---|
| 12 3 2 4 3 2 5 2 3 5 7 1 3 2 2 2 3 3 5 5 | 37 6 3 |
Sample test explanation
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].
