题目描述

给定一个序列 $a$ ，每次给定一个 $l,r$ ，求区间内一对 $x,y$ 满足 $x,y∈[l,r]$ 且 $[l,r]$ 内出现过的元素都在 $[x,y]$ 中出现过，请你最小化 $y-x+1$ 的大小并输出。

输入格式

一行两个正整数 $n,q$，分别表示序列长度，询问次数

一行 $n$ 个正整数 $a_i$ ，表示序列 $a$

下面 $q$ 行 每行两个正整数 $l,r$ ，表示询问区间

输出格式

输出 $q$ 行，表示每个询问的答案

样例 #1

样例输入 #1

10 10
10 10 6 1 4 6 4 6 10 6 
3 5
10 10
2 8
7 8
6 9
5 10
9 10
5 10
4 9
2 4

样例输出 #1

3
1
4
2
3
3
2
3
6
3

提示

对于 $10\%$ 的数据， $n \leq 10 \ ,\ q \leq 10$ 。

对于 $60\%$ 的数据， $n \leq 50\ ,\ q \leq 50$ 。

对于 $80\%$ 的数据， $n \leq 200\ ,\ q \leq 200$。

对于 $100\%$ 的数据， $n\leq2000\ ,\ q \leq 2000 \ ,\ a_i\leq2000$。