Highest Priced Pastry Query

You are given a list of pastry prices and several queries. The pastries are indexed from 1 to n. For each query, your task is to determine the maximum price in the inclusive range [l, r].

Efficiently answering these queries is essential, so consider using data structures like a segment tree for range maximum queries.

Mathematical Formulation:

Given an array \(A[1\dots n]\), for a query \( (l, r) \), output \( \max_{l \leq i \leq r} A_i \).

inputFormat

The input is given via stdin as follows:

1. The first line contains two integers \(n\) and \(q\) --- the number of pastries and the number of queries.
2. The second line contains \(n\) integers representing the prices of the pastries.
3. Each of the next \(q\) lines contains two integers \(l\) and \(r\) (with \(1 \leq l \leq r \leq n\)) representing a query.

outputFormat

For each query, output one line containing a single integer --- the maximum pastry price in the given range.

The output is written to stdout.

## sample

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

4
5
9

</p>