Un tanar pasionat de calatorii are o lista cu muzee virtuale si, pentru fiecare, cate un singur interval orar, in care acesta poate fi vizitat online, gratuit. Tanarul dispune zilnic de acelasi interval orar pentru vizite; un muzeu este convenabil daca poate fi vizitat online gratuit in timpul disponibil si daca pentru vizita ii poate aloca cel putin o ora. Muzeele din lista sunt numerotate cu valori naturale consecutive, incepand cu 1, si cel putin unul este convenabil.
Fisierul text bac.in contine cel mult 10^5 linii, iar pe fiecare linie cate o pereche de numere, reprezentand limitele cate unui interval orar: pe prima linie intervalul orar de care tanarul dispune zilnic, iar pe fiecare dintre urmatoarele linii, intervalul orar de vizitare gratuita pentru cate un muzeu, in ordinea din lista. Limitele intervalelor sunt ore fixe, numere naturale din intervalul [8,22], iar cele aflate pe aceeasi linie a fisierului sunt in ordine strict crescatoare si sunt separate printr-un spatiu.
Se cere sa se afiseze pe ecran, separate printr-un spatiu, doua valori, reprezentand numarul de muzee convenabile, respectiv numarul de ordine al ultimului astfel de muzeu din lista tanarului. Utilizati un algoritm eficient din punctul de vedere al timpului de executare si al memoriei utilizate.
Exemplu: daca fisierul contine valorile 16 19 15 18 17 21 19 21 18 20 12 13 atunci pe ecran se afiseaza numerele 3 4 (pot fi vizitate trei muzee cu numerele de ordine 1, 2 si 4, in intervalele 16-18, 17-19, respectiv 18-19).
- Date de intrare
- Fisierul bac.in: intervalul disponibil pe prima linie, cate un interval de muzeu pe fiecare linie urmatoare.
- Date de iesire
- Numarul de muzee convenabile si numarul de ordine al ultimului muzeu convenabil.
- Restrictii
- cel mult 10^5 muzee, ore in [8,22]
Exemple
Exemplul 1
Intrare
16 19 15 18 17 21 19 21 18 20 12 13
Iesire
3 4
Exemplul 2
Intrare
8 22 8 9
Iesire
1 1