Highest Rated Item

You are given N items, each with an associated rating, and Q queries. For each query, you are provided with two integers L and R which represent a range (inclusive) of item indices (1-indexed). Your task is to determine the index of the item with the highest rating in the specified range. In case of a tie (multiple items with the same maximum rating), you should return the smallest index among them.

Mathematically, for each query, you need to find the index i in the range \( L \leq i \leq R \) such that

[ ratings[i-1] = \max_{L \leq j \leq R} (ratings[j-1]) ]

and if there exists more than one such index, choose the smallest one.

Input Example:

5 3
4 2 5 3 5
1 3
2 4
1 5

Output Example:

3
3
3

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two integers N (the number of items) and Q (the number of queries) separated by a space.
2. The second line contains N space-separated integers, where the i^th integer represents the rating of the i^th item.
3. The following Q lines each contain two space-separated integers L and R representing a query.

outputFormat

For each query, output a single line containing one integer, which is the index of the highest-rated item in the specified range. If multiple items have the same highest rating, output the smallest index among them.

## sample

5 3
4 2 5 3 5
1 3
2 4
1 5

3
3
3

</p>