Minimum Covering Subinterval Query

Given a sequence of length \( n \) and \( q \) queries, each query is specified by two indices \( l \) and \( r \) (1-indexed). For each query, let \( S = \{a_i \mid l \le i \le r\} \) be the set of numbers that appear in the query interval. Your task is to find the shortest subinterval \( [l', r'] \) (which can be anywhere in the sequence) such that all numbers in \( S \) appear in \( [l',r'] \); in other words, \( \{a_i : l \le i \le r\} \subseteq \{a_i : l' \le i \le r'\} \). Output the length of this subinterval, i.e. \( r' - l' + 1 \).

Note: The subinterval \( [l',r'] \) you choose can extend outside \( [l, r] \) if it allows a reduction in the overall length while still covering all numbers from \( S \).

inputFormat

The first line contains two integers \( n \) and \( q \) representing the length of the sequence and the number of queries respectively.
The second line contains \( n \) integers denoting the sequence.
Each of the following \( q \) lines contains two integers \( l \) and \( r \) representing a query interval.

outputFormat

For each query, output a single integer — the length of the shortest subinterval \( [l',r'] \) (i.e. output \( r'-l'+1 \)) such that all numbers that appear in \( [l,r] \) appear in \( [l',r'] \).

sample

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

3
3
2