任务排行榜

Grade 100 Open Time Thursday, 18 June 2020, 10:45 AM
Discount 0.8 Time Discount Thursday, 18 June 2020, 10:45 AM
Allow late Yes Close Time Thursday, 18 June 2020, 10:45 AM
Input file task.in Output file task.out

【题目描述】任务排行榜(task)NYOJ 123

N个魔法师编号依次为1~N,魔法师工会会长经常会询问某一段编号内的魔法师完成任务数最高的人和完成任务数最低的人,并计算出两个人的差值。

现在,请你写一个程序,帮助会长回答每次的询问吧。

【输入格式】

只有一组测试数据。

第一行是两个整数N,Q,其中N表示魔法师的总数,Q表示会长询问的次数 (1<N≤100 000,1<Q≤1 000 000) 。

随后的一行有N个整数Vi(0≤Vi<100 000 000),分别表示每个人的完成任务数。

再之后的Q行,每行有两个正整数m和n,表示会长询问的是第m号魔法师到第n号魔法师。

【输出格式】

对于每次询问,输出第m号魔法师到第n号魔法师之间所有魔法师完成任务数的最大值与最小值的差。

【输入样例】

5 2

1 2 6 9 3

1 2

2 4

【输出样例】

1

7