Maximum Duplicate Gap in a Range

You are given a sequence of integers. Your task is to answer multiple queries. In each query, given an interval \([l, r]\), you need to find the maximum distance between the positions of any two identical numbers in the specified interval.

For any number \(x\) that appears more than once in the interval, let its first and last occurrence within the interval be at positions \(i\) and \(j\) respectively. The gap for \(x\) is defined as:

[ \text{gap}(x) = j - i ]

Your goal is to output the maximum gap among all numbers in the interval. If no number appears at least twice in the interval, output 0.

inputFormat

The first line contains two integers \(n\) and \(q\), where \(n\) is the number of elements in the sequence and \(q\) is the number of queries.

The second line contains \(n\) integers representing the sequence.

The next \(q\) lines each contain two integers \(l\) and \(r\) denoting the interval (1-indexed).

\(1 \leq l \leq r \leq n\).

outputFormat

For each query, output a single integer representing the maximum gap between two identical numbers in the interval \([l, r]\). Output 0 if no duplicate exists in the interval.

sample

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

3
0
0