Alex este un elev foarte poznaș. Dorind să îi ofere o ocupație utilă, diriginta i-a dat un șir foarte lung de numere și o serie de întrebări. După ce și-a învățat lecția, Alex vă roagă să scrieți un program care să răspundă la întrebări cât mai eficient pentru a-l scuti de muncă și a demonstra tuturor că a devenit un băiat cuminte.
Cerință
Vi se dau , un șir de numere naturale și apoi interogări de forma .
Dacă , atunci să se afișeze numărul de numere distincte din intervalul închis de indici .
Dacă , atunci să se afișeze elementul cu frecvență maximă în (care apare de cele mai multe ori în intervalul ) și frecvența acestuia în interiorul intervalului. În cazul în care sunt mai multe elemente cu frecvență maximă se va afișa cel cu valoare minimă (cel mai mic dintre ele).
Date de intrare
Fișierul de intrare pozne.in conține:
- pe prima linie trei numere naturale nenule, și , cu semnificația din enunț;
- pe următoarea linie numere naturale nenule, reprezentând elementele șirului;
- pe următoarele linii, câte două numere naturale nenule, și .
Date de ieșire
Se va afișa în fișierul de ieșire pozne.out răspunsul cerinței cerute.
Restricții și precizări
-
# Punctaj Restricții 1 25 2 25 3 25 4 25
Exemplul 1
pozne.in
1 7 4
1 2 2 3 3 3 2
1 3
2 5
4 7
1 7
pozne.out
2
2
2
3
Explicație
Pentru prima interogare, intervalul are 2 numere distincte, 1 și 2.
Exemplul 2
pozne.in
2 8 4
4 4 2 2 2 3 4 3
1 4
3 6
1 8
5 8
pozne.out
2 2
2 3
2 3
3 2
Explicație
Pentru prima interogare, 4 apare de 2 ori, 2 apare de 2 ori. Cum 4 și 2 au frecveță maximă, se afișează cel cu valoare mai mică.