Longest Equal Subarray

You are given an array \(a_1, a_2, \ldots, a_n\) and \(q\) queries. A subarray \(v\) of length \(m\) is called legal if and only if after performing several operations, all of its elements become equal. An operation is defined as follows:

• Select four integers \(a, b, c, d\) satisfying \(1 \le a \le b \le m\) and \(1 \le c \le d \le m\) such that \(b-a+1 = d-c+1\) and \[ v_a \operatorname{\,or\,} v_{a+1} \operatorname{\,or\,} \cdots \operatorname{\,or\,} v_b = v_c \operatorname{\,or\,} v_{c+1} \operatorname{\,or\,} \cdots \operatorname{\,or\,} v_d, \] where \(\operatorname{or}\) denotes the bitwise OR operation.
• Copy the segment \([a, b]\) and overwrite the segment \([c, d]\) with it. Note: The intervals \([a, b]\) and \([c, d]\) may overlap.

One can prove that a subarray is legal if and only if all its elements are already equal. Therefore, for each query you need to find, within the given interval, the length of the longest contiguous subarray whose elements are identical.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\), representing the number of elements in the array and the number of queries, respectively.

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

Each of the next \(q\) lines contains two integers \(l\) and \(r\) \((1 \le l \le r \le n)\) representing a query on the subarray \([l, r]\).

outputFormat

For each query, output a single integer denoting the length of the longest contiguous subarray within \([l, r]\) that consists of equal elements.

sample

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

2
2
1