Dominating Courier Company

Byteasar works for the BAJ company, which sells computer games. The company cooperates with many courier companies that deliver games to its customers. Byteasar is inspecting the cooperation between BAJ and the courier companies by analyzing a log of delivered packages. Each package is delivered by a specific courier company. For a given time period (subarray), if a courier company delivered more than half of the packages, we say that it dominated that period.

More formally, given a subarray of length \(L\) (i.e. from index \(i\) to \(j\), where \(L=j-i+1\)), a courier company is dominating if its frequency in the subarray is greater than \(\frac{L}{2}\). If such a company exists, output its ID, otherwise output NONE.

inputFormat

The first line contains two integers \(n\) and \(q\) denoting the number of packages and the number of queries respectively.

The second line contains \(n\) space-separated integers, where each integer denotes the courier company ID that delivered the corresponding package.

Each of the following \(q\) lines contains two integers \(L\) and \(R\) (1-indexed), representing a query for the subarray from index \(L\) to index \(R\).

outputFormat

For each query, print one line containing the ID of the dominating courier company if one exists. Otherwise, print NONE.

sample

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

2
2
2