No submission language available for this problem.

Background

模拟过程，思考可能的算法，是重要的能力。 题目有误

Description

你被派去记录脉冲炮的爆炸强度，已知在 $i$ 时刻，传感器可以传回强度 $a_i$

现有 $q$ 次询问，问你在 $L$ ~ $R$ 时刻范围内，每段区间时刻中，爆炸强度最小值，并依次输出。

Format

Input

第一行一个整数 n 表示共 n 时刻

第二行 n 个整数，分别表示每个时候传回的强度

第三行一个整数 q 表示共 q 次询问

第四行开始的 q 行，每行两个整数 L，R 表示一次询问中的区间时刻

Output

有 q 行每行一个整数，分别对应每个区间时刻中，强度的最小值

Samples

5
3 5 1 3 0
3
1 2
2 5
4 5

3
0
0

Limitation

$5 \leq n, q \leq 10^6$

$0 \leq a_i \leq 10^7$