弱点

Grade 100 Open Time Thursday, 18 June 2020, 5:35 PM
Discount 0.8 Time Discount Thursday, 18 June 2020, 5:35 PM
Allow late Yes Close Time Thursday, 18 June 2020, 5:35 PM
Input file weakness.in Output file weakness.out

【题目描述】弱点(weakness)POJ 3264

为了找到小光战力布署的弱点,琪儿需要了解小光某一段连续的堡垒中最多的飞船数与最少的飞船数的差。简而言之,就是在一组数中,查询某个区间内的最大数与最小数的差。

【输入格式】

第一行为N(1≤N≤50 000)和Q(1≤Q≤200 000)表示N个数和Q个查询,从第2行到第N+1行,每行一个数字,表示第i个堡垒的飞船数ai(1≤ai≤1000 000),从第N+2行到第N+Q+1行,每行两个整数A和B(1≤A≤B≤N),表示询问区间为(A,B)。

【输出格式】

第一行到第Q行,每行一个整数,表示从区间(A,B),最大数与最小数的差。

【输入样例】

6 3

1

7

3

4

2

5

1 5

4 6

2 2

【输出样例】

6

3

0