题目描述

黑猫老师年底要购物置办年货，奈何工资有限，只选择范围内最便宜的。

第一行一个整数 N，接下来 N 行，每行一个整数，表示商品价格。

接下来一行一个整数 Q，表示黑猫老师总共询问的次数。

接下来每行分别描述一个询问，为两个整数 $L_i$, $R_i$，表示黑猫老师询问的一个区间 $[L_i, R_i]$。

输入格式

对于每个黑猫老师的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：标号在区间 $[L_i, R_i]$ 中的所有商品中最便宜商品的价格。

输出格式

输出共M行，每行输出一个数，表示对一个问题的回答。

10 
7334 
1556 
8286 
1640 
2699 
4807 
8068 
981 
4120 
2179 
5 
3 4 
2 8 
2 4 
6 8 
7 10

1640 
981 
1556
981
981

提示

对于100%的数据，满足 $N≤10^6$，$Q≤10^6$, $1≤L_i≤R_i≤N$，$0<weight_i≤10^4$。