互斥子串

题目描述

Orange有一个序列 $a_i$，其中的每个元素均为互斥的，这意味着在一个合法的子串中，不能同时出现两个以上的 $a_i$，形式化的说，一个合法的子串 $a[l...r]$ 满足 $\forall_{i \ne j} \ a_i \ne a_j$，即其中所有的数都不相同。

Orange有 $q$ 次询问，每次询问给出 $l,r$，你需要回答 $a[l ... r]$ 中最长的合法的子串的长度是多少。

子串指的是序列中连续的一段子序列。

输入格式

第一行两个整数 $N,M$，$N$ 表示序列长度，$M$ 表示询问的次数。

第二行 $N$ 个整数 $a_i$。

接下来 $M$ 行每行两个整数 $l,r$，表示 Orange 询问的区间。

注意，序列的下标索引从0开始。

数据范围

$1\le N,M\le 2\times 10^5$ $0\le L\le R\le N-1$ $|a_i|\le 10^6$

输出格式

对于每组询问，输出一行，包含一个整数，表示答案。

样例 #1

样例输入 #1

9 2
2 5 4 1 2 3 6 2 4
0 8
2 6

样例输出 #1

6
5