Max Power Subarray

You are given an array A of N integers and Q queries. Each query is represented by two integers L and R (1-indexed) defining a subarray A[L...R]. For each query, you must traverse the subarray from index L to R and compute a value called the power of the subarray.

The power is calculated as follows: Let \(S\) be an initially empty set and current_power be 0. For each element \(a_i\) (with index \(i\)) in the subarray, if \(a_i \notin S\), add it to \(S\) and update current_power as \(current_power = current_power + a_i\). At each step, record the maximum value of current_power. Formally, if you process indices \(i = L, L+1, \ldots, R\), let \[ current\_power_i = \begin{cases} current\_power_{i-1} + a_i & \text{if } a_i \text{ is not seen before} \\ current\_power_{i-1} & \text{otherwise} \end{cases} \] The answer for the query is \(\max_{i=L}^{R} (current\_power_i)\>.

Your task is to compute the power for each query on the given array.

inputFormat

The first line contains two integers N and Q separated by a space.

The second line contains N integers representing the elements of the array A.

Then Q lines follow, each containing two integers L and R representing a query (1-indexed).

outputFormat

For each query, output the maximum power (as defined above) of the subarray on a new line.

## sample

6 2
1 2 3 -1 4 5
1 4
2 6

6
13

</p>