Numero minimo e frequenza
Vi viene fornito un array di
n interi positivi e q query. Ogni query richiede di trovare il numero minimo in un determinato sottoarray e quante volte tale valore minimo compare all’interno del sottoarray. Scrivete un programma in grado di gestire queste query in modo efficiente.Input
La prima riga contiene due interi
n e q (1 ≤ n, q ≤ 100 000), separati da uno spazio, che indicano rispettivamente la dimensione dell’array e il numero di query.La riga successiva contiene
n interi (1 ≤ a_i ≤ 10^9), separati da spazi, che rappresentano gli elementi dell’array.
Le successive q righe rappresentano le query: ognuna è composta da due interi l e r, separati da uno spazio, che indicano gli indici sinistro e destro del sottoarray.Output
Per ogni query, stampate due interi separati da uno spazio: il numero minimo del sottoarray e il numero di volte in cui tale valore minimo appare all’interno del sottoarray.
Esempi
Input | Output |
5 3
3 2 5 2 1
1 3
2 4
1 5 | 2 1
2 2
1 1 |
Constraints
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 3 MB