Nameless Beacon Prefixes

Time limit: 5000 msMemory limit: 256 MB

An exploration log contains $N$ transmissions. Transmission $i$ records a numeric beacon ID $A_i$ . Because different stations may assign different numeric IDs to the same underlying beacons, only the pattern of repeated IDs matters.

Two sequences $X = (X_1, X_2, \ldots, X_m)$ and $Y = (Y_1, Y_2, \ldots, Y_m)$ are renaming-equivalent if, for every pair of positions $p$ and $q$ satisfying $1 \le p, q \le m$ ,

X_p = X_q \quad\Longleftrightarrow\quad Y_p = Y_q.

Thus, equal IDs must correspond to equal IDs, and different IDs must correspond to different IDs, but the numeric values themselves do not need to match.

For each query, two nonempty ranges $[\ell_1, r_1]$ and $[\ell_2, r_2]$ are given. Find the largest integer satisfying

1 \le K \le \min(r_1 - \ell_1 + 1,\ r_2 - \ell_2 + 1)

such that the two prefixes

(A_{\ell_1}, A_{\ell_1+1}, \ldots, A_{\ell_1+K-1})

and

(A_{\ell_2}, A_{\ell_2+1}, \ldots, A_{\ell_2+K-1})

are renaming-equivalent.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N, Q \le 10^5$ ), the number of transmissions and the number of queries.

The second line contains integers (), the recorded beacon IDs.

Output

For each query, print one integer: the largest valid value of $K$ for the two specified ranges.

Samples

Sample 1

Input

12 4
4 9 4 2 9 2 7 1 7 8 1 8
1 6 7 12
1 6 2 7
3 6 8 12
5 6 11 12

Output

The first pair of ranges has the same repetition pattern for all $6$ positions. In the second pair, the first $2$ positions have the same pattern, while position $3$ is a repeat in one prefix and a new ID in the other. The remaining answers are $3$ and $2$ , respectively.

Nameless Beacon Prefixes

Input

Output

Samples

Sample 1

Submit

Submissions