Maximum-Minimum Difference

View as PDF

Submit solution


Points: 10
Time limit: 2.0s
PyPy 2 4.0s
PyPy 3 4.0s
Memory limit: 64M
PyPy 2 125M
PyPy 3 125M

Author:
Problem type

As a student, you're probably lazy. Realizing that, jsumabat has decided to decrease the word length of this problem and to keep it simple:

Given an array N with Q subarray queries, you are to find the maximum and minimum values of the subarrays, and output the difference of the two.

Note: Solutions that are unintended and pass will result in an attempt of jsumabat to create a test case that fails your solution.

Constraints

1 \le N \le 10^4

1 \le Q \le 10^5

1 \le a_i \le b_i \le N

The values of the array are positive integers that can be up to 10^9.

Input Specification

The first line contains two integers, N and Q.

The next line contains N integers, representing the values of the array in order (from 1 to N).

The last Q lines will contain two integers, a_i and b_i, the 1-indexed query.

Output Specification

For each query, output the maximum number in the subarray - the minimum number in the subarray.

Sample Input 1

6 4
1 3 9 4 3 5
1 2
2 5
4 6
4 5

Sample Output 1

2
6
2
1

Comments

There are no comments at the moment.