#P18830. [Croatian CPC2019] Bliski Brojevi

[Croatian CPC2019] Bliski Brojevi

[Croatian CPC2019] Bliski Brojevi

题目描述

有 nn 堆盘子,各堆的盘子数恰好构成 11 至 nn 的一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n。

你需要回答 qq 个询问。每个询问给出 l,rl,r,求第 ll 堆至第 rr 堆之间,任意两堆盘子数之差的绝对值的最小值,即

min⁡l≤i<j≤r∣pi−pj∣.\min_{l\le i<j\le r}|p_i-p_j|.

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤3×1041\le n,q\le3\times10^4)。

第二行包含 nn 个整数,表示 11 至 nn 的一个排列 pp。

接下来 qq 行,每行包含两个整数 l,rl,r(1≤l<r≤n1\le l<r\le n),表示一个询问。

输出格式

输出 qq 行,第 ii 行包含一个整数,表示第 ii 个询问的答案。

样例 1

输入

7 5
5 2 3 6 1 4 7
3 5
5 7
1 2
3 6
2 7

输出

2
3
3
1
1