Minimum Number and Frequency
You are given an array of
n positive integers and q queries. Each query asks for the minimum number in a given subarray and the number of occurrences of that minimum value within the subarray. Write a program to efficiently process these queries.Input
The first line contains two integers
n and q (1 ≤ n, q ≤ 100 000), separated by a space, representing the size of the array and the number of queries, respectively. The next line contains
n integers q lines represent the queries. Each query consists of two integers l and r, separated by a space, representing the left and right indices of the subarray.Output
For each query, print two integers separated by a space: the minimum number in the subarray and the number of occurrences of that minimum value within the subarray.
Examples
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