Most Frequent Element in Subarrays

You are given an array of integers and several queries. Each query specifies a subarray by its 1-indexed starting and ending positions. For each query, your task is to determine the most frequent element in the specified subarray. If more than one element qualifies, choose the smallest one.

More formally, for a query with indices \(L\) and \(R\), consider the subarray \(A[L], A[L+1], \dots, A[R]\). Let \(freq(x)\) denote the number of occurrences of element \(x\) in the subarray. You need to find the element \(x\) such that \(freq(x)\) is maximized. If there are multiple \(x\) with the maximum frequency, return the smallest \(x\).

Constraints: You may assume that the size of the array and the number of queries are small enough so that a simple approach is efficient.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

The third line contains an integer \(q\) representing the number of queries.

Each of the next \(q\) lines contains two integers \(L\) and \(R\) (1-indexed), denoting the starting and ending indices of a query.

outputFormat

For each query, output the most frequent element in the subarray on a new line.

## sample

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

2
2
1

</p>