How to solve the following problem? Given an array A of size N and M queries to solve. Each element in the array is less or equal than the size of the array.

N < 50000, M < 500000

Each query consist in two numbers l and r. We must answer what is the most frequent value (the one who appears more times) in the subarray A[l], A[l+1], ... , A[r-1], A[r]. If there are many posibilities answer the smallest.