Majority Element Query

You are given an array A of N integers and Q queries. Each query consists of two integers l and r (1-indexed). For each query, you are to determine the majority element in the subarray A[l...r]. A majority element in a subarray is defined as an element that appears more than \(\lfloor\frac{r-l+1}{2}\rfloor\) times in that subarray.

If a majority element exists, output its value; otherwise, output \(-1\). Note that if a majority element exists, all its occurrences in the specified subarray are identical, so the minimum among those values is the element itself.

inputFormat

The first line contains two space-separated integers N and Q — the number of elements in the array and the number of queries.

The second line contains N space-separated integers representing the array A.

Each of the next Q lines contains two space-separated integers l and r, denoting a query on the subarray A[l...r].

outputFormat

For each query, print a single line containing the majority element if it exists, or \(-1\) if it does not.

## sample

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

3
-1
4

</p>