描述

给定n个整数，从1到n顺序编号，接下来进行m次查询，第i次查询第$a_i$个数到第$b_i$个数（包含$a_i$和$b_i$）之间的最小值并输出。

例如：

n = 8, 8个正整数依次为：40, 20, 10, 30, 70, 50, 80, 60

m = 3，3次查询分别为：

a_1 = 3, b_1 = 7；

a_2 = 1, b_2 = 2；

a_3 = 5, b_3 = 8；

第一次查询：第3个数（10）到第7个数（80）之间最小值是10；

第二次查询：第1个数（40）到第2个数（20）之间最小值是20；

第三次查询：第5个数（70）到第8个数（60）之间最小值是50；

故输出 10

20

50

输入输出格式

输入

第一行输入一个整数n ( $1≤n≤10^5$ )，表示整数的数量

第二行输入n个整数（ $0≤整数≤10^5$ ）

第三行输入一个整数m ( $1≤m≤10^5$ )，表示查询次数

接下来m行，每行输入2个整数$a_i$和$b_i$（ $1≤a_i≤b_i≤n$ ），分别表示查询的起始位置和终止位置

输出

输出共m行，每行输出一个整数，分别表示每次查询得到的第$a_i$个数到第$b_i$个数之间（包含$a_i$和$b_i$）的最小值

样例输入输出

8
40 20 10 30 70 50 80 60
3
3 7
1 2
5 8

10
20
50