最小値と頻度

n 個の正の整数からなる配列と q 個のクエリが与えられます。各クエリでは、指定された部分配列における最小値と、その最小値が部分配列内で出現する回数を求める必要があります。これらのクエリを効率的に処理するプログラムを作成してください。

入力

最初の行には、配列の大きさを表す整数 n と、クエリの数を表す整数 q がスペース区切りで与えられます (1 ≤ n, q ≤ 100 000)。

次の行には、配列の要素を表す n 個の整数 () が、スペース区切りで与えられます。

出力

各クエリに対して、部分配列の最小値と、その最小値が部分配列内で出現する回数を、スペース区切りで出力してください。

例