Summer FLASG Beginner | Veverița

ASG s-a jucat foarte foarte foarte mult Fortnite. S-a dus la mall și a cumpărat o pușcă NERF. Apoi, a început sa fugăreasca prin parc o veveriță cu multe nuci. Dupa ce a alergat-o prin toată Peninsula Balcanică, a ajuns la vizuina ei din Iași. Acolo, aceasta i-a spus lui ASG că-i poate da un anumit număr de nuci pentru a o lăsa in pace. Cum veverița are foarte multe nuci și ASG adoră nucile, a decis să negocieze cu ea. Până la urmă, s-au hotărât că vor scrie pe o foaie un șir $a$ de $N$ elemente ce denotă greutățile nucilor. Veverița îi va da apoi lui ASG $T$ intervale închise de forma $[x, y]$, cu proprietatea că ASG poate lua câte o nucă dacă este inclusă greutatea ei in respectivul interval. Dat fiind că sunt mai multe intervale, ASG poate lua o nucă de o anumită greutate de mai multe ori. Cum veverița este magică, are un număr infinit de nuci, șirul $a$ exprimând doar greutățile pe care le are în stoc.

Cerință

Ajutați-l pe ASG să afle câte nuci poate lua acasă cât mai rapid, ca să plece din Iași înainte să afle Flaviu că este în același oraș cu el.

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $T$.
Pe a doua linie se găsesc $N$ numere naturale, elementele șirului $a$.
Pe urmatoarele $T$ linii se găsește câte o pereche de două numere naturale, $x$ și $y$, cu semnificațiile din enunț.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, numărul de nuci pe care le ia ASG acasă.

Restricții și precizări

• $1 \leq N, T \leq 500 \ 000$;
• $0 \leq a_i \leq 1 \ 000 \ 000 \ 000$;
• $0 \leq x, y \leq 1 \ 000 \ 000 \ 000$.

Exemplul 1

stdin

5 3
1 2 3 4 5
1 3
2 4
1 5

stdout

11

Explicație

Avem $3$ intervale de analizat.
în intervalul $[1, 3]$ se află $3$ numere naturale din șirul $a$. ($1$, $2$, $3$);
În intervalul $[2, 4]$ se află $3$ numere naturale din șirul $a$. ($2$, $3$, $4$);
În intervalul $[1, 5]$ se afla $5$ numere naturale din șirul $a$. ($1$, $2$, $3$, $4$, $5$).
În total, avem $3$ + $3$ + $5$, adică ASG ia acasă $11$ nuci.

Exemplul 2

stdin

1 3
4
1 3
1 4
4 4

stdout

2

Explicație

Avem $3$ intervale de analizat.
în intervalul $[1, 3]$ nu se află niciun număr din șirul $a$, dat fiind că este format doar din 4.
În intervalul $[1, 4]$ se găsește elementul $4$.
În intervalul $[4, 4]$ singurul element este $4$, exact elementul din șirul $a$.
În total, avem $1$ + $1$, adică ASG ia acasă $2$ nuci.