Maximum Books Query

You are given n sections, each containing a certain number of books. You will also be given q queries. For each query, determine the maximum number of books in the contiguous range of sections specified by the indices l and r (1-indexed).

Note: The sections are numbered from 1 to n and each query is independent.

inputFormat

The first line of input contains two integers n and q, representing the number of sections and the number of queries respectively. The second line contains n space-separated integers, where the i-th integer represents the number of books in the i-th section. This is followed by q lines, each containing two integers l and r, representing a query that asks for the maximum number of books in the sections from index l to r (inclusive).

outputFormat

For each query, output a single line containing the maximum number of books found in the sections between indices l and r (inclusive).## sample

5 3
2 1 5 3 4
1 3
2 4
3 5

5
5
5