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