cenzura

Se dă $N$ și $a_1 \ a_2 \ \dots \ a_N$. Se dau $Q$ interogări de forma $l$, $r$. La a $i$-a interogare, vei alege numerele $l$ și $r$ ($1 \leq l \leq r \leq N$) și vrei să știi care ar fi maximul șirului și de câte ori ar apărea acesta în șir dacă s-ar cenzura subsecvența $[l..r]$.

• Subsecvența $[l..r]$ a unui șir este șirul $a_l \ a_{l+1} \ a_{l+2} \dots a_r$
• Prin a cenzura o subsecvență $[l..r]$, înțelegem a înlocui $a_i$ cu $0$, pentru fiecare $l \leq i \leq r$. De exemplu, dacă cenzurăm subsecvența $[2..4]$ a șirului $[1, 2, 3, 4, 5, 6, 7]$, obținem șirul $[1, 0, 0, 0, 5, 6, 7]$.

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $Q$.

Pe a doua linie se află un șir de $N$ numere naturale, reprezentând șirul $a$.

Pe următoarele $Q$ linii se află câte o pereche de numere $l$, $r$.

Date de ieșire

Se vor afișa, pe $Q$ linii răspunsurile interogărilor. A $i$-a linie va conține două numere, reprezentând răspunsul la a $i$-a întrebare.

Restricții și precizări

• $1 \leq N, Q \leq 10^6$
• $1 \leq a_i \leq 10^9$
• Pentru $44$ de puncte, $N, Q \leq 5 \ 000$

Exemplul 1

stdin

9 6
3 2 3 1 6 7 5 7 7
1 2
1 3
3 6
6 9
1 9
2 8

stdout

7 3
7 3
7 2
6 1
0 9
7 1

Explicație

$N = 9$, $Q = 6$, iar $a = [3, 2, 3, 1, 6, 7, 5, 7, 7]$.

La prima interogare, dacă cenzurăm subsecvența ($1$, $2$), șirul obținut este $[0, 0, 3, 1, 6, 7, 5, 7, 7]$, maximul fiind $7$ și apare de $3$ ori.

La a treia interogare, dacă cenzurăm subsecvența ($3$, $6$), obținem șirul $[3, 2, 0, 0, 0, 0, 5, 7, 7]$, maximul fiind $7$ și apare de $2$ ori.

La a patra interogare, dacă cenzurăm subsecvența ($6$, $9$), obținem șirul $[3, 2, 3, 1, 6, 0, 0, 0, 0]$, maximul fiind $6$ și apare o singură dată.

La a cincea interogare, dacă cenzurăm subsecvența ($1$, $9$), obținem șirul $[0, 0, 0, 0, 0, 0, 0, 0, 0]$, maximul fiind $0$ și apare de $9$ ori.