问题描述

给定一个序列 $a$，该序列长度为 $n$。

给定 $m$ 组查询，每组查询给出两个数字 $l,r$（$1\le l\le r\le n$）。你需要输出 $a_{l\sim r}$ 的最大值。

输入格式

第一行输入一个正整数 $n$，表示序列长度。$(1\le n\le 10^5)$

接下来一行输入 $n$ 个正整数 $a_i$。$(1\le a_i\le 10^9)$

接下来一行输入一个正整数 $m$，表示查询数。$(1\le m\le 10^4)$

接下来 $m$ 行每行输入两个正整数 $l,r$。（$1\le l\le r\le n$）

输出格式

对于 $m$ 组查询，每组需要输出 $a_{l\sim r}$ 的最大值。

样例输入

6
32 21 27 882 21 9
4
2 4
2 5
1 3 
2 2

样例输出

882
882
32
21