暂无测试数据。

Description

Jim是一位宝石收藏品行家，在他的收藏室里保存着许多珍贵的宝石，磷叶石、钻石、摩根石、透绿柱石….，已知Jim有\(n\)个宝石，现在他将这\(n\)个宝石从\(1\)到\(n\)排开编号从\(1\)到\(n\)。Jim发现他所有的宝石中竟然有不少是完全相同的的，我们规定每个宝石都有一个特征值\(a_i\)，当两个宝石特征值相等时及认为两个宝石相同。Jim发现两个相同的宝石离得越接近越明显。Jim现在有\(m\)个问题，他想问你在.编号\(l\)到\(r\)这一区间里的所有宝石中，两个相同宝石的最近距离是多少，（两个宝石的距离是它们编号的绝对值之差）。

保证 \(l < r\) ，对于 \(a_x\)和\(a_y\) 若\(a_x=a_y\) 它们的距离为\(|x-y|\)。

Format

Input

单组测试数据。
第一行有两个整数\(n, m (1≤n,m≤2 \times 10^5)\)，表示宝石序列的长度和查询的次数。
第二行有\(n\)个整数\(a_1,a_2,...,a_n (-10^9 \leq a_i \leq 10^9)\)，\(a_i\)表示第\(i\)个宝石的特征值。
接下来有\(m\)行，每一行给出两个整数\(l_j,r_j (1 \leq l_j \leq r_j \leq n)\)表示一个查询。

Output

对于每一个查询，输出最近的距离，如果没有相等的元素，输出\(-1\)。

Sample 1

Input

5 3
1 1 2 3 2
1 5
2 4
3 5

Output

1
-1
2

Limitation

2s, 128MiB for each test case.

Hint

样例解释

第一个询问 第一个和第二个宝石最近且相同 距离为\(1\)
第二个询问 第二个宝石到第四个宝石之间没有相同宝石 输出\(-1\)
第三个询问 第三个宝石和第五个宝石最近且相同 距离为\(2\)

数据范围

对于 10%的数据 保证 \(n \leq 20\)
对于 50%的数据 保证 \(n \leq 50000\)
对于 100%的数据 保证 \(n \leq 200000\)

Source

CSP 2019 模拟测试题（三）