Cerința

Chimmy are un șir de N numere întregi și Q întrebări de forma a b, unde pentru fiecare întrebare Chimmy dorește să afle, pe parcurgerea șirului de la poziția a la poziția b, de câte ori se schimbă maximul. Chimmy, neștiind să programeze, vă cere să îl ajutați pentru 100 de puncte!

Date de intrare

Programul citește de la tastatură numerele N și Q, după care va citi N numere, reprezentând șirul.

Următoarele Q linii vor conține câte două numere a și b, cu semnificația din enunț.

Date de ieșire

Se va afișa pe câte o linie răspunsul la fiecare întrebare.

Restricții și precizări

• Se recomandă folosirea fastio
• 1 ≤ N ≤ 1.000.000
• 1 ≤ Q ≤ 1.000.000
• 1 ≤ a, b ≤ N
• numerele tabloului se pot reprezenta pe 32 de biți cu semn
• parcurgerile de la a la b nu vor fi întotdeauna de la stânga la dreapta. De exemplu, dacă a = 5 și b = 3, indicii se vor parcurge în ordinea 5, 4, 3.

Exemplu:

Intrare

7 5
4 6 1 3 5 2 8
3 7
4 6
1 7
6 1
5 5

Ieșire

4
2
3
3
1

Explicație

În secvența [1, 3, 5, 2, 8], maximul se schimbă de 4 ori (1, 3, 5, 8).

În secvența [3, 5, 2], maximul se schimbă de 2 ori (3, 5).

În secvența [4, 6, 1, 3, 5, 2, 8], maximul se schimbă de 3 ori (4, 6, 8).

În secvența [2, 5, 3, 1, 6, 4], maximul se schimbă de 3 ori (2, 5, 6) (secvența [6, 1] a fost parcursă invers).

În secvența [5], maximul se schimbă o singură dată (5).