While I was solving a different problem recently, I noticed an interesting variation I hadn’t seen before. So, I decided to formalize it and share it here as a fun challenge!

The problem is a query-based extension of the classic “Longest Subarray with Contiguous Elements” problem.

Problem Statement:-

You are given an array of integers arr of size N. You need to answer Q queries. Each query specifies a subarray [L, R] (1-based indices) and asks:

“What is the length of the longest contiguous subarray within arr[L..R] whose elements form consecutive integers in any order?”

Notes:

The subarray must be contiguous in the original array.

Elements can appear in any order inside the subarray.

A subarray is valid if all elements are distinct and:

max(subarray) — min(subarray) + 1 == length(subarray)

Input Format First line: N Q Second line: arr[1] arr[2] ... arr[N] Next Q lines: L R

Constraints:

1 ≤ N ≤ 10^4

1 ≤ Q ≤ 10^3

-10^5 ≤ arr[i] ≤ 10^5

1 ≤ L ≤ R ≤ N

Output Format

For each query, print a single integer — the length of the longest valid consecutive subarray within [L,R].

Sample Input 1 6 2 1 5 4 6 3 2 1 6 2 5

Sample Output 1 6 4