Se da un sir de n numere naturale ordonat crescator si T intervale inchise [x, y]. Determinati cate dintre aceste intervale nu contin niciun element al sirului.
- Date de intrare
- Pe prima linie se afla n. Pe a doua linie se afla cele n numere ale sirului, in ordine crescatoare. Pe a treia linie se afla T, iar pe urmatoarele T linii cate doua numere x si y, cu x <= y.
- Date de iesire
- Se afiseaza un singur numar: cate intervale nu contin niciun element al sirului.
- Restrictii
- 1 <= n <= 100 000 1 <= T <= 200 000 Toate numerele sunt naturale, cuprinse intre 1 si 1 000 000 000. Sirul poate contine valori egale.
Exemple
Exemplul 1
Intrare
5 3 7 7 12 20 7 1 2 4 6 7 7 13 19 21 50 8 12 1 100
Iesire
4
Exemplul 2
Intrare
1 10 3 10 10 9 9 11 11
Iesire
2