题目描述

N 个整数排成一排，形成一个序列 S。

如果一个连续子序列中不存在相同的元素，则把该子序列称作“无同子序列”。

现在问你 Q 个问题，每个问题形如 A B，表示需要你从序列 S 的第 A 个元素与第 B 个元素之间找出该区间内的最长“无同子序列”。你只需要输出其长度。

输入格式

第一行：包含两个整数 N, Q；

第二行：包含 N 个整数 Si；

接下来 Q 行，每行包含两个整数 A, B。

输出格式

共 Q 行，每个问题的答案占一行。

5 2
2 5 -1 2 2
1 5
4 5

3
1

数据范围

100% 的数据：$1 ≤ N, Q ≤ 2×10^5, |S _i| ≤ 10^6, 1 ≤ A ≤ B ≤ N。$