Problem C: AC

上一题 正确率: $2.50\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $40$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数据结构

Description

zj带领这N个coder ，coder编号分别为1~N ,zj经常爱拿某一段编号AC数量最多的人与AC最少的人进行比较，计算机出两个人AC的AC数差值，用这种方法既能鼓励AC数高的人，同事也算是批评AC数少的人。

所以zj经常问FJH coder第i号到第j号coder中，AC数最高的人，与AC数最低的人之间相差多少题

现在你来写个程序，帮帮FJH来回答每次询问吧

Input

只有一组测试数据
第一行是两个整数N,Q，其中N表示coder的总数。Q表示zj询问的次数。(1<N<=100000,1<Q<=1000000)
随后的一行有N个整数Vi(0<=Vi<100000000)，分别表示每个人的AC数。
再之后的Q行，每行有两个正正数m,n，表示zj询问的是第m号coder到第n号coder。

Output

对于每次询问，输出第m号coder到第n号coder之间所有AC数的最大值与最小值的差。

Sample Input复制

5 2
1 2 6 9 3
1 2
2 4

Sample Output复制

1
7