Maximum Subinterval with Fewer Distinct Values

You are given a sequence \(a\) of length \(n\) with indices from \(1\) to \(n\), and \(m\) query operations. For each query, you are given an interval \([l, r]\). Your task is to find a subinterval \([l', r']\) such that \(l \le l' \le r' \le r\) and the number of distinct values in \([l', r']\) is less than the number of distinct values in the original interval \([l, r]\). Among all subintervals satisfying this condition, the one with the maximum length \(r' - l' + 1\) should be chosen. If no such subinterval exists, output \(0\).

Note: In other words, you need to remove all occurrences of at least one distinct element that appears in \([l, r]\) while keeping the subinterval contiguous, and maximize the length of the remaining subinterval.

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the length of the sequence and the number of queries, respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the sequence.

Then \(m\) lines follow, each containing two integers \(l\) and \(r\) indicating a query.

outputFormat

For each query, output a single integer on a new line — the maximum length of a subinterval \([l', r']\) of \([l, r]\) that has fewer distinct values than \([l, r]\). If no valid subinterval exists, output \(0\).

sample

4 2
1 2 1 2
1 4
2 3

1
1