[PC015] The Strongest Warriors

In the kingdom of Numeria, the Coliseum of Warriors is filled with a sequence of \(n\) warriors, each with a positive strength value.

The king enjoys watching but is very demanding: for any segment of warriors he points to, he wants to know:

• Who is the mightiest warrior (the maximum strength in that range)?
• How many warriors share that same peak strength?

The scribes must answer quickly, or risk angering the king. You have been summoned to write a program that answers the king’s queries.

Input

The first input line contains two inters integer \(n\) and \(q\), respectively the amount of warriors and queries.

The second line contains \(n\) integers \(w_1, w_2, \ldots, w_n\): the strength of the warriors in the sequence.

The next \(q\) lines describe the queries: each contains two integers \(a \, b\) describing the query range.

Output

\(q\) lines, each with two integers separated by a space describing the answer to the respective query:

• The first integer should be the maximum strength in the range \([a,b]\) (that is, from the \(a\)-th warrior to the \(b\)-th warrior, inclusive).
• The second integer should be the amount of warriors in the range with that maximum strength.

Constraints

• \( 1 \leq n \leq 10^5 \)
• \( 1 \leq q \leq 10^5 \)
• \( 1 \leq w_i \leq 10^9 \)
• \( 1 \leq a \leq b \leq n\)

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

5 3
5 2
5 1
3 1

• Query 1 (1–6): The range is [2, 5, 1, 5, 3, 5], the maximum is 5 and it appears 3 times.
• Query 2 (2–4): The range is [5, 1, 5, 3], the maximum is 5 and it appears 2 times.
• Query 3 (3–5): The range is [1, 5, 3], the maximum is 5 and it appears once.
• Query 4 (5–5): The range is [3], the maximum is 3 and it appears 3 once.