U427491 小明的铁路 I

小明修建了一条玩具铁路，TA 邀请你来玩，TA 在这条铁路上放置了一些奖品，TA 会给定一段区间 $[l,r]$ TA 允许你在这段区间内随意拿走一件奖品，你想拿到最大价值的奖品，你会如何做呢？

第一行，$n$ 表示铁路的长度。 第二行，输入 $n$ 个数，表示每个位置上奖品的价值。 第三行，$q$ 表示询问次数。 接下来 $q$ 行，每行两个数 $l$,$r$ 表示区间的左右端点。

对于每次询问输出最大价值。

$1\le n,q \le 10^6$ $a_i\le 10^9$ $1\le l \le r \le n$