题目描述

给定 $n$ 个整数 $a_1,a_2,\dots,a_n$，及 $q$ 次询问，每次询问给定两个参数 $l$ 与 $r$，请求出 $a_l,\dots,a_r$ 范围内最长的不重复段的长度。

所谓不重复段，是指一个序列中，连续的、所有数字互不相同的子序列。

输入格式

• 第一行，两个整数 $n,q$
• 第二行， $n$ 个整数，表示 $a_1,...,a_n$
• 接下来 $q$ 行，每行 $2$ 个整数，表示每次询问区间的左右端点 $L_i,R_i$

输出格式

输出共 $n$ 行，每行一个整数表示询问的答案

5 2
1 1 2 3 2
1 3
2 5

2
3

样例解释 1

对于第1个询问：第1个数至第3个数之间，最长不重复段为[1,2]，长度为2。 对于第2个询问：第2个数至第5个数之间，最长不重复段为[1,2,3]，长度为3。

数据范围

• 对于 $30\%$ 数据，$1 \leq n,q \leq 10$；
• 对于 $60\%$ 数据，$1 \leq n,q \leq 1,000$；
• 对于 $100\%$ 数据，$1\leq n,q\leq 100,000$ , $1\leq a_i \leq 10^6$ , $1 \leq L \leq R \leq n$。