Número Mínimo e Frequência
Tem à sua disposição um array de
n inteiros positivos, bem como q consultas. Cada consulta solicita o menor valor existente numa determinada subarray e o número de ocorrências desse valor mínimo nessa mesma subarray. Crie um programa para processar estas consultas de forma eficiente.Entrada
A primeira linha contém dois inteiros
n e q (1 ≤ n, q ≤ 100 000), separados por um espaço, que representam, respetivamente, o tamanho do array e o número de consultas.A linha seguinte contém
n inteiros (1 ≤ a_i ≤ 10^9), separados por espaços, que representam os elementos do array. Nas q linhas seguintes, cada linha descreve uma consulta através de dois inteiros l e r, separados por um espaço, que correspondem ao índice esquerdo e ao índice direito da subarray em análise.Saída
Para cada consulta, imprima dois inteiros separados por um espaço: o número mínimo na subarray e o número de ocorrências desse valor mínimo dentro da subarray.
Exemplos
Entrada | Saída |
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