Given an array A consisting of n integers and q queries, each represented as a tuple (l,r). The task is to determine the index of the smallest value within the subarray Al,Al+1,…,Ar for each query.
### Input
- The first line contains two integers n,q.
- The second line contains n integers Ai.
- The next q lines, each line contains two integers l,r, a query.
### Output
- Print the answer for each query. If there multiple indices with the same minimum value, print the smallest one.
### Constraints
- 1≤n,q≤105.
- 1≤Ai≤109.
- 1≤l≤r≤n.
### Example
Input:
4214311423
Output:
13
