Problem
連続する配列要素の最大値を効率的に計算するデータ構造を実装します。
入力
最初の行には、1 つの自然数
N (
\(1 <= N <= 100000\)) — が含まれています。配列内の数字の数。 2 行目には、1 から 100000 までの
N 個の数字が含まれます — 3 行目には 1 つの自然数
K (
\(1 <= K <= 30000\)) が含まれます &mdash ;最大値を計算するためのリクエスト数。 次の
K 行に、それぞれ 2 つの数値を入力します —配列セグメントの左右の要素の番号 (配列の要素は 1 から数えられると想定されます)。
インプリント
クエリごとに、配列の指定された範囲内の最大要素の値を出力します。数値をスペース区切りで 1 行に出力します。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
5
2 2 2 1 5
2
23
25 |
2 5 |